Back to DSA

Kth Smallest Element in a BST

medium
Acceptance: 49%
BST

In a binary search tree, find the element with the k-th smallest value. The parameter k is 1-indexed, meaning k=1 asks for the minimum element.

Examples

Example 1:
Input:root = [7,3,10,1,5], k = 2
Output:3
Example 2:
Input:root = [4,2,6,1,3,5,7], k = 5
Output:5

Hints

Related Problems

Validate Binary Search TreemediumLowest Common Ancestor of a BSTmediumRecover Binary Search Treehard
00:00
import java.util.*;

class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode curr = root;
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            k--;
            if (k == 0) return curr.val;
            curr = curr.right;
        }
        return -1;
    }
}
Time complexityO(H + k)
Space complexityO(H)