Kth Smallest Element in a BST

Master this topic with zero to advance depth.

Kth Smallest Element in a BST

Find kth val.

Medium

Approach 1

Level I: Inorder Traversal to Array

Intuition

As with any BST problem, the inorder traversal gives us the elements in strictly increasing order. We can perform a full inorder traversal, store the results in an array, and then simply return the element at index k-1.

Thought Process

Traverse the tree (Left, Node, Right).
Append values to a list.
Return list[k-1].

⏱ O(N) (visiting each node)💾 O(N) (to store all node values)

Detailed Dry Run

Tree	Inorder Array	k	Result
[3,1,4,null,2]	[1, 2, 3, 4]	1	1

java

import java.util.*;

public class Main {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> nodes = new ArrayList<>();
        inorder(root, nodes);
        return nodes.get(k - 1);
    }
    private void inorder(TreeNode node, List<Integer> nodes) {
        if (node == null) return;
        inorder(node.left, nodes);
        nodes.add(node.val);
        inorder(node.right, nodes);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(1);
        root.left.right = new TreeNode(2);
        root.right = new TreeNode(4);
        System.out.println(new Main().kthSmallest(root, 1)); // 1
    }
}

Approach 2

Level II: Divide and Conquer (using Node counts)

Intuition

If we can efficiently count the number of nodes in a subtree, we can determine whether the $k$ -th smallest element lies in the left subtree, is the root itself, or lies in the right subtree.

Logic

Let L = countNodes(root.left).
If k == L + 1: root.val is the result.
If k <= L: Search in the left subtree.
If k > L + 1: Search in the right subtree for the (k - L - 1)-th smallest element.

⏱ O(N) (O(N^2) if tree is skewed and countNodes is O(N))💾 O(H)

Detailed Dry Run

k=1, L=2 (nodes in left). k<=L -> Search Left. L=1 (at next level). k<=L -> Search Left. L=0. k=1, L=0 -> k=L+1 -> Result found.

java

public class Main {
    public int kthSmallest(TreeNode root, int k) {
        int leftCount = countNodes(root.left);
        if (k == leftCount + 1) return root.val;
        if (k <= leftCount) return kthSmallest(root.left, k);
        return kthSmallest(root.right, k - leftCount - 1);
    }
    private int countNodes(TreeNode n) {
        if (n == null) return 0;
        return 1 + countNodes(n.left) + countNodes(n.right);
    }
}

Approach 3

Level III: Optimal (Iterative Inorder with Early Exit)

Intuition

Thought Process

We don't need to visit all $N$ nodes if $k$ is small. By using an iterative inorder traversal with a stack, we can visit nodes one by one in increasing order. As soon as we reach the $k$ -th node, we return its value and stop the traversal.

Complexity

Time: $O(H + k)$ where $H$ is the height of the tree.
Space: $O(H)$ for the stack.

⏱ O(H + k)💾 O(H)

Detailed Dry Run

Stack	Current Node	k-count	Action
[3, 1]	null	0	Pop 1, Push 2
[3]	2	1	Pop 1 was 1st smallest.
[3]	null	1	Pop 2, k reaches 1 (if k=2)

java

public class Main {
    public int kthSmallest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        while (true) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (--k == 0) return root.val;
            root = root.right;
        }
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the $k=0$ condition. Since $k$ is 1-indexed (1st smallest), we decrement $k$ and check k == 0 immediately after popping.

← Previous QuestionPath Sum II

Next Question →Populating Next Right Pointers in Each Node

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.