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, return the kth smallest value (1-indexed) of all the values of the nodes in the tree. The BST property guarantees that an inorder traversal visits nodes in ascending order.

Example 1:

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

Example 2:

text
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Sample Input
—
Sample Output
—
Constraints
  • 1 <= k <= n <= 10^4
  • 0 <= Node.val <= 10^4
Test Cases
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

Approach: Inorder Traversal

Perform an inorder traversal of the BST, which visits nodes in sorted order. Count visited nodes and return the value when the count reaches k.

javascript
function kthSmallestElementInABst(root, k) {
  let count = 0, result = 0;
  function inorder(node) {
    if (!node || count >= k) return;
    inorder(node.left);
    count++;
    if (count === k) { result = node.val; return; }
    inorder(node.right);
  }
  inorder(root);
  return result;
}

Time Complexity: O(H + k) where H is tree height

Space Complexity: O(H)

Saved in this browser only. Private to you.

JavaScript