Kth Smallest Element in a BST | Problems

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:

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

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

Tree Binary Tree DFS

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.

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.