DSA With AI
Week 4 ยท Trees

Kth Smallest Element in a BST

Return the kth smallest value in a BST. The key is that inorder traversal of a BST visits values in sorted order.

Medium Trees Week 4 Practice runner

Frame the problem

  • k is 1-based.
  • The tree is a valid BST.
  • You can stop traversal as soon as the kth value is visited.
1. Reveal example inputs and outputs

Example 1

Input:

kth_smallest([
  3,
  [
    1,
    null,
    [
      2,
      null,
      null
    ]
  ],
  [
    4,
    null,
    null
  ]
], 1)

Output:

1

Example 2

Input:

kth_smallest([
  1,
  null,
  null
], 1)

Output:

1
2. Brute force first

How would you solve this if the tree were not a BST? Which BST property removes the need to sort all values?

3. Reveal the insight ladder
  1. Inorder traversal visits left subtree, node, then right subtree.
  2. For a BST, that order is ascending.
  3. Count nodes as they are visited in inorder.
  4. When the count reaches k, return the current value.
4. Dry run before code
  1. Tree [3, 1, 4, null, 2], k = 1.
  2. Inorder visits 1 first.
  3. The first visited value is the answer.
  4. For k = 3 in a larger tree, continue until the third inorder visit.
5. Reveal final Python solution 
def kth_smallest(root, k):
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node[1]
        node = stack.pop()
        value, left, right = node
        k -= 1
        if k == 0:
            return value
        node = right

Complexity: Time O(h + k) when stopping early, space O(h) for the stack.

Interview narration

  • I will exploit the BST's sorted inorder traversal.
  • The iterative stack avoids collecting every value.
  • Stopping at k is better than doing a full traversal when k is small.

Common traps

  • Using preorder or level order and losing sorted order.
  • Returning the kth node visited with zero-based counting by mistake.
  • Collecting all values when the interviewer asks for an early-stop approach.

Follow-up drills

1. What if kth queries are repeated many times?

Augment each node with subtree sizes. Then you can decide whether k falls in the left subtree, at the current node, or in the right subtree in O(h) per query.

2. What if the tree can be modified between queries?

Maintain subtree sizes during insert/delete operations, or use a balanced order-statistics tree if available.

3. What if the BST allows duplicates?

Clarify ordering and counting semantics. If duplicates are separate nodes, inorder still yields non-decreasing order and each node counts as one visit.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.