Kth Smallest Element in a BST
Given the root of a binary search tree, and an integer k, return the kth smallest element in the BST.
Constraints:
- The number of nodes in the tree is in the range [1, 10^4].
- 1 <= k <= n.
- Follow up: If the BST is modified often (i.e., we can insert/delete nodes of the BST), how would you optimize your findKthSmallest routine?
Examples:
Input: [3,1,4,null,2], k = 1
Output: 1
Explanation: The first smallest element is 1.
Input: [5,3,6,2,4,null,null,1], k = 3
Output: 3
Explanation: The third smallest element is 3.
Solutions
Inorder Traversal
Time: O(n)Space: O(n)
We use a stack to store the nodes of the BST. We start from the root and keep going left until we reach a null node. Then we pop a node from the stack, decrement k, and if k is 0, we return the value of the current node. Otherwise, we move to the right subtree of the current node.
class Solution:
def kthSmallest(self, root:
TreeNode, k:
int) -> int:
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
k -= 1
if k == 0:
return current.val
current = current.rightFollow-up:
If the BST is modified often, we can use a data structure like a balanced BST or a heap to optimize the findKthSmallest routine.
