Kth Smallest Element in a BST

Medium
1914.

Kth Smallest Element in a BST

Kth Smallest Element in a BST is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.

Given the root of a binary search tree with distinct values and an integer k, return the k-th smallest value in the tree (counting from 1).

Example 1

Input
root = [3,1,4,null,2], k = 1
Output
1
Explanation
In increasing order the values are 1, 2, 3, 4; the first is 1.

Example 2

Input
root = [5,3,6,2,4,null,null,1], k = 3
Output
3
Explanation
In increasing order the values are 1, 2, 3, 4, 5, 6; the third is 3.

Example 3

Input
root = [2,1], k = 2
Output
2
Explanation
The largest of two values is the second smallest.

Constraints

  • 1 <= k <= number of nodes <= 10^4
  • 0 <= Node.val <= 10^4
  • all node values are distinct
  • root is a valid binary search tree

Follow-up: If the tree were modified often (inserts and deletes) and you had to answer this query many times, how would you speed it up?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * 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) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Kth Smallest Element in a BST — Problem & Solution

Kth Smallest Element in a BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Kth Smallest Element in a BST is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the root of a binary search tree with distinct values and an integer k, return the k-th smallest value in the tree (counting from 1).

Example 1

Input: root = [3,1,4,null,2], k = 1
Output: 1
Explanation: In increasing order the values are 1, 2, 3, 4; the first is 1.

Example 2

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: In increasing order the values are 1, 2, 3, 4, 5, 6; the third is 3.

Example 3

Input: root = [2,1], k = 2
Output: 2
Explanation: The largest of two values is the second smallest.

Constraints

  • 1 <= k <= number of nodes <= 10^4
  • 0 <= Node.val <= 10^4
  • all node values are distinct
  • root is a valid binary search tree

Follow-up: If the tree were modified often (inserts and deletes) and you had to answer this query many times, how would you speed it up?

Hints for Kth Smallest Element in a BST

  1. Hint 1

    An in-order traversal (left, node, right) of a binary search tree lists its values in increasing order.

  2. Hint 2

    You do not need the whole sorted list — only its k-th entry.

  3. Hint 3

    Run the in-order traversal iteratively with a stack and stop the moment the k-th node is popped.

How to solve Kth Smallest Element in a BST

In-order traversal visits a binary search tree's values in increasing order, so the k-th node it visits holds the answer; an explicit stack lets the walk stop right there.

Approach

  1. Start with an empty stack and cur = root.
  2. Push cur and move left until cur is null.
  3. Pop a node and decrease k; if k reaches 0, return the node's value.
  4. Otherwise set cur to the popped node's right child and repeat.

Why it works

For every node, in-order visits all of its (smaller) left subtree, then the node, then its (larger) right subtree, so by induction the nodes are popped in increasing order of value. The k-th pop is therefore the k-th smallest value.

Complexity

  • Time — O(h + k), h the height of the tree
  • Space — O(h)

Pitfalls

  • k counts from 1.
  • For the follow-up, store each node's subtree size: the rank of the root is then known and the search descends one side, O(h) per query.

Reference solution

Python

from typing import Optional

def kthSmallest(root: Optional[TreeNode], k: int) -> int:
    stack = []
    node = root
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        k -= 1
        if k == 0:
            return node.val
        node = node.right
    return -1

Java

public static int kthSmallest(TreeNode root, int k) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root;
    while (!stack.isEmpty() || node != null) {
        while (node != null) { stack.push(node); node = node.left; }
        node = stack.pop();
        if (--k == 0) return node.val;
        node = node.right;
    }
    return -1;
}

C++

int kthSmallest(TreeNode* root, int k) {
    vector<TreeNode*> stack;
    TreeNode* node = root;
    while (!stack.empty() || node) {
        while (node) { stack.push_back(node); node = node->left; }
        node = stack.back();
        stack.pop_back();
        if (--k == 0) return node->val;
        node = node->right;
    }
    return -1;
}

JavaScript

var kthSmallest = function(root, k) {
    var stack = [], node = root;
    while (stack.length > 0 || node !== null) {
        while (node !== null) { stack.push(node); node = node.left; }
        node = stack.pop();
        if (--k === 0) return node.val;
        node = node.right;
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals