# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def kthLargest(self, root: TreeNode, k: int) -> int:
        self.k_largest = None
        def dfs(root: TreeNode, cur_index: int) -> int:
            if not root:
                return cur_index
            cur_index = dfs(root.right, cur_index)
            if cur_index == k - 1:
                self.k_largest = root.val
            print(cur_index)
            cur_index += 1
            cur_index = dfs(root.left, cur_index)
            return cur_index
        dfs(root, 0)
        return self.k_largest


if __name__=='__main__':
    root = TreeNode(3)
    root.left = TreeNode(1)
    root.right = TreeNode(4)
    root.left.right = TreeNode(2)
    s = Solution()
    print(s.kthLargest(root, 1))
