Kth Smallest Element in a BST

medium
TreesTreeBinary TreeDepth-First Search

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.

Examples

Example 1

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

Example 2

  • Input: root = [5,3,6,2,4,null,null,1], k = 3
  • Output: 3
  • Explanation: The sorted values are [1, 2, 3, 4, 5, 6], and the 3rd smallest is 3.

Constraints

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Recursive Inorder Traversal

Intuition

An inorder traversal of a BST visits nodes in ascending order. We can leverage this property to find the kth smallest element by performing an inorder traversal and counting nodes as we visit them. When our counter reaches k, the current node holds the answer. We can either collect all values into a sorted list and return the kth element, or use a counter to stop early once we reach the kth node.

Algorithm

  1. Perform an inorder traversal of the BST (left, node, right).
  2. Maintain a counter that increments each time a node is visited.
  3. When the counter equals k, record the current node's value as the result.
  4. Return the recorded result.
TimeO(n) in the worst case, O(h + k) on averageSpaceO(h) where h is the height of the tree

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int count = 0;
        int result = 0;
        inorder(root, k, count, result);
        return result;
    }

private:
    void inorder(TreeNode* node, int k, int& count, int& result) {
        if (node == nullptr) return;
        inorder(node->left, k, count, result);
        count++;
        if (count == k) {
            result = node->val;
            return;
        }
        inorder(node->right, k, count, result);
    }
};
Java 21
class Solution {
    private int count = 0;
    private int result = 0;

    public int kthSmallest(TreeNode root, int k) {
        count = 0;
        result = 0;
        inorder(root, k);
        return result;
    }

    private void inorder(TreeNode node, int k) {
        if (node == null) return;
        inorder(node.left, k);
        count++;
        if (count == k) {
            result = node.val;
            return;
        }
        inorder(node.right, k);
    }
}
Python 3.12
def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    count = [0]
    result = [0]

    def inorder(node):
        if not node:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)

    inorder(root)
    return result[0]
Go 1.26
func kthSmallest(root *TreeNode, k int) int {
    count := 0
    result := 0
    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        count++
        if count == k {
            result = node.Val
            return
        }
        inorder(node.Right)
    }
    inorder(root)
    return result
}
Approach 2

Iterative Inorder with Stack

Intuition

We can avoid recursion by using an explicit stack to simulate inorder traversal. This gives us more control over when to stop and avoids potential stack overflow for very deep trees. We push nodes onto the stack as we go left. When we can go no further left, we pop a node (visiting it in inorder), decrement k, and check if k has reached zero. If so, we have found our answer. Otherwise, we move to the right subtree and continue.

Algorithm

  1. Initialize an empty stack and set the current node to root.
  2. While the stack is not empty or current is not null, push current and move left.
  3. When current is null, pop from the stack (this is the next smallest element).
  4. Decrement k. If k equals 0, return the popped node's value.
  5. Set current to the popped node's right child and continue the loop.
TimeO(h + k)SpaceO(h)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stk;
        TreeNode* current = root;
        while (current != nullptr || !stk.empty()) {
            while (current != nullptr) {
                stk.push(current);
                current = current->left;
            }
            current = stk.top();
            stk.pop();
            k--;
            if (k == 0) return current->val;
            current = current->right;
        }
        return -1;
    }
};
Java 21
class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            k--;
            if (k == 0) return current.val;
            current = current.right;
        }
        return -1;
    }
}
Python 3.12
def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    current = root
    while current or stack:
        while current:
            stack.append(current)
            current = current.left
        current = stack.pop()
        k -= 1
        if k == 0:
            return current.val
        current = current.right
    return -1
Go 1.26
func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    current := root
    for current != nil || len(stack) > 0 {
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        k--
        if k == 0 {
            return current.Val
        }
        current = current.Right
    }
    return -1
}

Frequently asked questions

What is the optimal time complexity of Kth Smallest Element in a BST?

The most efficient approach in this guide ("Iterative Inorder with Stack") runs in O(h + k) time and uses O(h) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Kth Smallest Element in a BST use?

Kth Smallest Element in a BST is a medium-level Trees problem involving Tree, Binary Tree, Depth-First Search. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Kth Smallest Element in a BST be solved without extra space?

The most space-efficient approach in this guide uses O(h) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(h) where h is the height of the tree, while the optimized version uses O(h).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Related Problems

Validate Binary Search Tree

Original problem: leetcode.com

Loading editor...
Input
root=
[3,1,4,null,2]
k=
1
Expected Output
1