Kth Smallest Element in a BST
Problem Description
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.
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
Constraints:
- The number of nodes in the tree is
n. - 1 <= k <= n <= 104
- 0 <= Node.val <= 104
Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
Solve it on LeetCode
Approaches
1. Inorder Traversal with List
Intuition:
A Binary Search Tree (BST) has the property that an inorder traversal (left-root-right) of the tree gives the nodes in non-decreasing order. By performing an inorder traversal and storing the elements in a list, we can easily access the kth smallest element by retrieving the element at index k-1 from the list.
Code:
- Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node exactly once.
- Space Complexity: O(N) for the list used to store inorder traversal.
2. Inorder Traversal with Counter
Intuition:
By maintaining a counter while doing the inorder traversal, we can stop the traversal as soon as the kth element is found. This avoids storing all elements, thereby saving space.
Code:
- Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we visit each node once.
- Space Complexity: O(H), where H is the height of the tree. This accounts for the recursive stack space.
3. Iterative Inorder Traversal
Intuition:
We can simulate the recursive inorder traversal using an explicit stack. This allows us to handle trees iteratively, which can be more space efficient in specific scenarios.
Code:
- Time Complexity: O(N), where N is the number of nodes in the tree. We simulate the inorder traversal iteratively.
- Space Complexity: O(H), where H is the height of the tree, due to the stack used in the iterative approach.