230. Kth Smallest Element in a BST

url: https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

💻 Code

Approach :

• In the binary tree, inorder counts elements as increasing sequence.

1. Iteration Inorder

• TC: $O(h + k)$
  • $h$: height
• SC: $O(n)$

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        while True:
            while root:
                stack.append(root)
                root = root.left
            root = stack.pop()
            k -= 1

            if k == 0:
                return root.val
            
            root = root.right

This iterative solution effectively traces the graph to identify the process and provides a clear and intuitive understanding of how the algorithm works.

2. Inorder Recursion

• TC: $O(n)$
• SC: $O(n)$

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        def in_order(node):
            if node is None:
                return []

            return in_order(node.left) + [node.val] + in_order(node.right)

        return in_order(root)[k - 1]    # k - 1, because 1-indexed

This recursion solution reorganize all elements as an inorder. However, it stores whole elements before giving the answer. Thus, $O(n)$.

3. Optimal Inorder Recursion

• TC: $O(h + k)$
• SC: $O(n)$

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        res = []

        def in_order(node, res, k):
            if len(res) < k and node is not None:
                in_order(node.left, res, k)
                res.append(node.val)
                in_order(node.right, res, k)

        in_order(root, res, k)

        return res(root)[k - 1]    # k - 1, because 1-indexed

This improved version of recursion automatically stops when it gets to the kth smallest element.