Kth Smallest Element in a BST Medium 0 attempts
LeetCode ↗

Kth Smallest Element in a BST

Medium TreeBinary TreeDFS LeetCode

Given the root of a binary search tree and an integer k, find the kth smallest value stored in the tree (using 1-based counting). Because of how a BST is ordered, visiting its nodes inorder naturally produces them from smallest to largest, which is worth keeping in mind here.

Input Format
Implement kthSmallestElementInABst(root, k). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [3,1,4,null,2]
k = 1
Output
1

Example 2

Input
root = [5,3,6,2,4,null,null,1]
k = 3
Output
3
Constraints
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4
Test Cases (2)
Case 1
Args: [[3,1,4,null,2],1] Expected: 1
Case 2
Args: [[5,3,6,2,4,null,null,1],3] Expected: 3
Topics
TreeBinary TreeDFS

Iterative Inorder

Inorder traversal visits a BST in sorted order. Stop after visiting k nodes.

javascript
function kthSmallestElementInABst(root, k) {
  const stack=[];let current=root;
  while(current||stack.length) {
    while(current){stack.push(current);current=current.left;}
    current=stack.pop();if(--k===0)return current.val;current=current.right;
  }
}

Time: O(h + k) | Space: O(h) auxiliary space

Saved in this browser only. Private to you.

JavaScript