Problem

Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest element in the tree.

A BST has an important property:

  • Every value in the left subtree is smaller than the current node.
  • Every value in the right subtree is greater than the current node.

Example:

    4
   / \
  2   6
 / \ / \
1  3 5  7

The values in sorted order are:

1, 2, 3, 4, 5, 6, 7

If k = 4, the answer is 4.

The Key Observation

The biggest hint is that the tree is a Binary Search Tree, not just a binary tree.

If we traverse a BST using inorder traversal:

Left → Node → Right

we visit the nodes in ascending sorted order.

For the previous example:

        4
       / \
      2   6
     / \ / \
    1 3 5 7

The inorder traversal visits:

1 → 2 → 3 → 4 → 5 → 6 → 7

That means:

  • 1st smallest = first node visited
  • 2nd smallest = second node visited
  • kth smallest = kth node visited

This completely avoids sorting anything.

Approach 1 — Recursive Inorder DFS

Your recursive solution performs an inorder traversal while counting how many nodes have been visited.

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

        def dfs(node):
            if not node:
                return

            dfs(node.left)

            self.index += 1
            if self.index == k:
                self.res = node.val
                return

            dfs(node.right)

        dfs(root)
        return self.res

How it works

Imagine this BST:

      5
     / \
    3   7
   / \
  2   4

Suppose:

k = 3

Step 1

Start at 5.

Go left.

      5
     /
    3

Step 2

Go left again.

      5
     /
    3
   /
  2

There is no further left child.

Visit 2.

Visited = 2
index = 1

Step 3

Return to 3.

Visit it.

Visited = 3
index = 2

Step 4

Go right.

Visit 4.

Visited = 4
index = 3

Since

index == k

the answer is

4

Why does inorder traversal work?

Because BSTs are already partially sorted.

Every node satisfies:

Left < Node < Right

So visiting

Left
Node
Right

naturally produces values from smallest to largest.

This property is unique to BSTs.

Time Complexity

Every node is visited at most once.

Time

O(n)

Space

O(h)

where h is the tree height.

  • Balanced BST → O(log n)
  • Skewed BST → O(n)

The recursive call stack uses this space.

Approach 2 — Iterative Inorder Traversal (Recommended)

The recursive solution is elegant, but interviewers also expect you to know how to perform inorder traversal iteratively.

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

        while curr or stack:

            while curr:
                stack.append(curr)
                curr = curr.left

            curr = stack.pop()

            k -= 1
            if k == 0:
                return curr.val

            curr = curr.right

This simulates recursion using an explicit stack.

Why while curr or stack?

This is the standard iterative inorder template.

We continue while either:

  • we still have nodes to explore (curr), or
  • there are previously saved nodes waiting in the stack.

If both become empty, the traversal is complete.

Step-by-Step Example

Using the tree:

        4
       / \
      2   6
     / \ / \
    1 3 5 7

Initially:

curr = 4
stack = []

Go as far left as possible

Push every left node.

Push 4
Push 2
Push 1

Stack:

[4, 2, 1]

Pop

Pop 1.

Visited = 1

This is the smallest value.

Then move to its right child.

There isn't one.

Continue

Pop 2.

Visited = 2

Move to 3.

Push 3.

Pop 3.

Visited = 3

Continue.

Eventually the visitation order becomes

1
2
3
4
5
6
7

Exactly the same order as recursive inorder traversal.

Why not use a normal DFS?

A normal DFS like this:

stack = [root]

while stack:
    node = stack.pop()

    if node.left:
        stack.append(node.left)

    if node.right:
        stack.append(node.right)

does not preserve sorted order.

It simply visits nodes in depth-first order.

For example, it might produce:

4
6
7
5
2
3
1

or another DFS ordering depending on how children are pushed.

That ordering has nothing to do with the sorted values in the BST, so you cannot use it to find the kth smallest element.

The crucial insight is that this problem requires an inorder traversal, not just any DFS.

Common Mistakes

Forgetting inorder traversal

Using preorder or postorder won't produce sorted values.

Starting the counter incorrectly

Most solutions count from 1.

You can also start at 0 and increment before checking, as in your recursive solution.

Both approaches work as long as you're consistent.

Confusing tree traversal with array indexing

The problem states that k is 1-indexed.

This doesn't mean the tree itself is indexed.

It simply means:

1st smallest
2nd smallest
3rd smallest
...

There is no "0th smallest" node.

Which solution should you know?

For interviews:

  • ✅ Understand why inorder traversal gives sorted order.
  • ✅ Be comfortable writing the recursive inorder DFS.
  • ✅ Learn the iterative inorder template, as it's the standard non-recursive solution.

If you remember just one iterative tree traversal pattern, make it this inorder template—it appears in many BST interview problems.

Final Takeaways

  • A BST's inorder traversal visits nodes in ascending order.
  • The kth node visited during inorder traversal is the kth smallest element.
  • The recursive solution is concise and easy to understand.
  • The iterative solution uses a stack to simulate recursion and is the standard interview approach.
  • Ordinary DFS traversal is not enough—you specifically need inorder traversal to preserve the BST's sorted property.