noodleProblems/
Kth Smallest Element in a BST
#135

Kth Smallest Element in a BST

AlgorithmmediumTreeDepth First SearchBinary Search TreeBinary Tree

Given the root of a **binary search tree** and an integer k, return the k-th smallest value in the tree (1-indexed).

In a BST, an in-order traversal visits values in ascending order, so the k-th value produced by an in-order walk is the answer.

The tree is given as a level-order array where null marks a missing child: [3, 1, 4, null, 2].

Example cases

  • small
    in root = [3,1,4,null,2]1234k = 1
    out 1
    In-order is [1,2,3,4]; the 1st smallest is 1.
  • third
    in root = [5,3,6,2,4,null,null,1]123456k = 3
    out 3
    In-order is [1,2,3,4,5,6]; the 3rd smallest is 3.
  • single
    in root = [1]1k = 1
    out 1

Constraints

  • The number of nodes in the tree is n.
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4
Saved
root =
[3,1,4,null,2]
k =
1