230.-kth-smallest-element-in-a-bst.md

230. Kth Smallest Element in a BST

• Medium
• Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Analysis

The idea is first go to the left most child, which is the smallest one according to the definition of a binary search tree. Then we traverse the tree and find the k th one.

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        while root or stack:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1
            if k == 0:
                return root.val
            root = root.right