Kth Smallest Element in a BST (LC 230): Iterative Inorder

Find the k-th smallest value in a binary search tree. An inorder traversal visits BST values in sorted order, so stop after k pops of an explicit stack: O(h + k) time, O(h) space.

Language Selection

Choose your preferred programming language

Showing: Python

Kth Smallest Element in a BST

Problem Statement

You are given the root of a binary search tree and an integer k. Return the value that would be in position k (counting from 1) if every value in the tree were listed in ascending order.

In a binary search tree, every value in a node’s left subtree is smaller than the node’s value and every value in its right subtree is larger. All values in the tree are distinct, and k is always between 1 and the number of nodes.

Examples

Example 1:

Input: root = [5,3,8,2,4,null,9], k = 3
Output: 4
Explanation: In ascending order the values are 2, 3, 4, 5, 8, 9. The third one is 4.

Example 2:

Input: root = [6,2,7,1,4,null,null,null,null,3,5], k = 5
Output: 5
Explanation: Sorted, the values are 1, 2, 3, 4, 5, 6, 7, so the fifth smallest is 5.

Example 3:

Input: root = [10], k = 1
Output: 10
Explanation: A single-node tree; its only value is the smallest.

Constraints

  • The tree has n nodes, where 1 <= n <= 10^4
  • 1 <= k <= n
  • 0 <= Node.val <= 10^4
  • All node values are distinct, and the tree is a valid BST

Approach 1: Collect All Values and Sort

Algorithm

The simplest correct idea ignores the BST ordering entirely: gather every value, sort, and index.

  1. Walk the whole tree with an explicit stack (any traversal order works), appending each node’s value to a list.
  2. Sort the list in ascending order.
  3. Return the element at index k - 1.

This is a good opening answer in an interview because it is obviously correct, but it wastes the one property the problem gives you for free.

Implementation

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional


class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        values = []
        stack = [root] if root else []
        # Visit every node; the order does not matter because we sort afterwards
        while stack:
            node = stack.pop()
            values.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        values.sort()
        return values[k - 1]

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> values = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root != null) {
            stack.push(root);
        }
        // Visit every node; order is irrelevant because we sort afterwards
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            values.add(node.val);
            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        Collections.sort(values);
        return values.get(k - 1);
    }
}

Go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
import "sort"

func kthSmallest(root *TreeNode, k int) int {
	values := []int{}
	stack := []*TreeNode{}
	if root != nil {
		stack = append(stack, root)
	}
	// Visit every node; order is irrelevant because we sort afterwards
	for len(stack) > 0 {
		node := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		values = append(values, node.Val)
		if node.Left != nil {
			stack = append(stack, node.Left)
		}
		if node.Right != nil {
			stack = append(stack, node.Right)
		}
	}
	sort.Ints(values)
	return values[k-1]
}

JavaScript:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    const values = [];
    const stack = root ? [root] : [];
    // Visit every node; order is irrelevant because we sort afterwards
    while (stack.length > 0) {
        const node = stack.pop();
        values.push(node.val);
        if (node.left) stack.push(node.left);
        if (node.right) stack.push(node.right);
    }
    // Numeric comparator: the default sort compares values as strings
    values.sort((a, b) => a - b);
    return values[k - 1];
};

C#:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
using System.Collections.Generic;

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var values = new List<int>();
        var stack = new Stack<TreeNode>();
        if (root != null) {
            stack.Push(root);
        }
        // Visit every node; order is irrelevant because we sort afterwards
        while (stack.Count > 0) {
            TreeNode node = stack.Pop();
            values.Add(node.val);
            if (node.left != null) stack.Push(node.left);
            if (node.right != null) stack.Push(node.right);
        }
        values.Sort();
        return values[k - 1];
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        vector<int> values;
        stack<TreeNode*> st;
        if (root) st.push(root);
        // Visit every node; order is irrelevant because we sort afterwards
        while (!st.empty()) {
            TreeNode* node = st.top();
            st.pop();
            values.push_back(node->val);
            if (node->left) st.push(node->left);
            if (node->right) st.push(node->right);
        }
        sort(values.begin(), values.end());
        return values[k - 1];
    }
};

Complexity Analysis

  • Time: O(n log n). Visiting all n nodes is O(n), and sorting the collected values dominates.
  • Space: O(n) for the list of values (the stack holds at most O(n) nodes as well).

Approach 2: Iterative Inorder Traversal with Early Stop (Optimal)

Algorithm

An inorder traversal (left subtree, node, right subtree) of a BST produces the values in ascending order. So the k-th node that inorder visits is exactly the answer, and there is no need to look at anything after it.

Using an explicit stack instead of recursion keeps the code safe on a degenerate tree (a “linked list” of 10^4 nodes would overflow Python’s default recursion limit) and makes stopping early trivial:

  1. Start with node = root and an empty stack.
  2. Push node and keep moving to node.left until it is null. The top of the stack is now the smallest value not yet visited.
  3. Pop a node. This is the next value in sorted order, so decrement k.
  4. If k reaches 0, return the popped node’s value.
  5. Otherwise move to the popped node’s right child and repeat from step 2.

Implementation

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from typing import Optional


class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        stack = []
        node = root
        while True:
            # Slide down to the smallest unvisited value
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            k -= 1
            if k == 0:
                return node.val
            # Everything in the right subtree comes next in sorted order
            node = node.right

Java:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode node = root;
        while (true) {
            // Slide down to the smallest unvisited value
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            if (--k == 0) {
                return node.val;
            }
            // Everything in the right subtree comes next in sorted order
            node = node.right;
        }
    }
}

Go:

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) int {
	stack := []*TreeNode{}
	node := root
	for {
		// Slide down to the smallest unvisited value
		for node != nil {
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		k--
		if k == 0 {
			return node.Val
		}
		// Everything in the right subtree comes next in sorted order
		node = node.Right
	}
}

JavaScript:

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(root, k) {
    const stack = [];
    let node = root;
    while (true) {
        // Slide down to the smallest unvisited value
        while (node) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        if (--k === 0) {
            return node.val;
        }
        // Everything in the right subtree comes next in sorted order
        node = node.right;
    }
};

C#:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
using System.Collections.Generic;

public class Solution {
    public int KthSmallest(TreeNode root, int k) {
        var stack = new Stack<TreeNode>();
        TreeNode node = root;
        while (true) {
            // Slide down to the smallest unvisited value
            while (node != null) {
                stack.Push(node);
                node = node.left;
            }
            node = stack.Pop();
            if (--k == 0) {
                return node.val;
            }
            // Everything in the right subtree comes next in sorted order
            node = node.right;
        }
    }
}

C++:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
#include <stack>
using namespace std;

class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> st;
        TreeNode* node = root;
        while (true) {
            // Slide down to the smallest unvisited value
            while (node) {
                st.push(node);
                node = node->left;
            }
            node = st.top();
            st.pop();
            if (--k == 0) {
                return node->val;
            }
            // Everything in the right subtree comes next in sorted order
            node = node->right;
        }
    }
};

Complexity Analysis

  • Time: O(h + k), where h is the height of the tree. Reaching the leftmost node costs O(h), and each of the k pops after that adds amortized O(1) work. In the worst case (a skewed tree, or k = n) this is O(n); in a balanced tree with small k it is O(log n + k).
  • Space: O(h) for the stack, which holds at most one root-to-leaf path at a time.

Key Insights

  1. Inorder of a BST is sorted. This single fact turns “k-th smallest” into “k-th node visited”.
  2. Stop as soon as you have the answer. Unlike Approach 1, the traversal never visits (pops) nodes that come after the k-th one in sorted order. It may push a few larger ancestors on the way down the left spine, but it stops before processing them.
  3. The stack is the recursion made visible. Each pushed node is a pending “visit me after my left subtree” task, which is why the stack never holds more than one path.
  4. Iterative beats recursive here. A sorted insertion order makes a BST with height n; an explicit stack has no recursion-depth limit to hit.

Edge Cases

  • Single node: [10], k = 1 returns 10 right after the first pop.
  • k = 1: the answer is the leftmost node; only the left spine is pushed.
  • k = n: the answer is the largest value, the last node visited.
  • Left-skewed tree (values inserted in descending order): the first inner loop pushes all n nodes, so the stack reaches size n.
  • Right-skewed tree (values inserted in ascending order): the stack never holds more than one node.
  • Value 0: a node with value 0 is valid; test node for null rather than for a falsy value when porting.

Common Mistakes

  1. Sorting numbers as strings in JavaScript. values.sort() without a comparator orders 10 before 9.
  2. Off-by-one on k. k is 1-based; the sorted list is 0-based, so the answer is at index k - 1.
  3. Recursing without an early exit. A recursive inorder that keeps walking after finding the answer turns O(h + k) into O(n).
  4. Using a global counter that is not reset. Storing the count in a field and calling the method twice gives wrong answers on the second call.
  5. Deep recursion. A recursive solution on a skewed tree of 10^4 nodes exceeds Python’s default limit of 1000 frames.

Interview Tips

  1. Say the key fact out loud early: “inorder traversal of a BST gives sorted order”.
  2. Offer the sort-everything approach first in one sentence, then move straight to the early-stopping traversal.
  3. State the complexity as O(h + k), not just O(n); it shows you understand why stopping early matters.
  4. Mention that you chose an iterative traversal to avoid recursion depth issues on skewed trees.
  5. Be ready for the follow-up about frequent updates; it is the most common extension of this problem.

Follow-up Questions

  1. The tree is modified often and k-th smallest is queried often. How do you speed it up? Store the size of each node’s subtree. At each node, compare k with leftSize + 1 to decide whether the answer is here, in the left subtree, or in the right subtree (with k reduced). Each query and each insert/delete then costs O(h), and O(log n) if the tree is kept balanced.
  2. Can you do it with O(1) extra space? Yes, with Morris inorder traversal, which temporarily threads each node’s inorder predecessor back to it and restores the tree as it goes.
  3. How would you find the k-th largest? Do a reverse inorder traversal (right, node, left) and stop after k pops.
  4. What if the tree were not a BST? Then inorder order means nothing; you would collect the values and use sorting or a size-k max-heap, O(n log k).