Find Kth Smallest in BST
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given the root of a binary search tree and an integer `k`. Return the value of the node that would appear in the `k`th position if all node values were listed in ascending order.
A binary search tree has the property that for every node:
- all values in the left subtree are smaller than the node value, and
- all values in the right subtree are larger than the node value.
You may assume `1 <= k <= number of nodes in the tree`.
Example:
- Input: root = [5,3,6,2,4,null,null,1], k = 3
- In-order traversal gives: [1,2,3,4,5,6]
- Output: 3
Discuss an efficient approach and analyze its time and space complexity.
Quick Answer: This question evaluates understanding of binary search tree properties, ordered data retrieval, and algorithmic efficiency in locating the k-th smallest element.
You are given the root of a binary search tree (BST) and an integer k. Return the value of the node that would appear in the kth position if all node values were listed in ascending order. A BST has the property that every value in a node's left subtree is smaller than the node's value, and every value in a node's right subtree is larger than the node's value. For this problem, the tree is provided as a level-order list where None represents a missing child.
Constraints
- 1 <= number of nodes in the tree <= 10000
- 1 <= k <= number of nodes in the tree
- All node values are unique integers
- -100000 <= node value <= 100000
- The input tree satisfies the binary search tree property
Examples
Input: ([5, 3, 6, 2, 4, None, None, 1], 3)
Expected Output: 3
Explanation: The in-order traversal is [1, 2, 3, 4, 5, 6], so the 3rd smallest value is 3.
Input: ([10], 1)
Expected Output: 10
Explanation: There is only one node, so the 1st smallest value is 10.
Hints
- What traversal of a BST visits values in ascending order?
- You do not need to store every value; count nodes as you visit them and stop when you reach k.