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:
n.1 <= k <= n <= 1040 <= 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?
In a Binary Search Tree (BST), an in-order traversal visits nodes in ascending order. To find the kth smallest element, perform an in-order traversal and count the nodes until you reach the kth one.
This solution uses a recursive in-order traversal to find the kth smallest element. We decrement k each time we visit a node and check if it reaches 0, signifying the kth element. If it does, we record the current node's value and exit further recursion.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(n) (due to recursion stack in worst case).
Morris Traversal is a way to perform in-order traversal with O(1) extra space. This method modifies the tree's structure temporarily to avoid the recursive call stack. This approach uses the concept of threading where leaf nodes point to their in-order successor to facilitate traversal.
This C implementation uses the Morris Traversal to avoid recursion. The traversal temporarily alters the tree's structure to keep track of each node's predecessor, thereby facilitating efficient space management.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| In-Order Traversal (Recursive) | Time Complexity: O(n), Space Complexity: O(n) (due to recursion stack in worst case). |
| Morris In-Order Traversal (Iterative) | Time Complexity: O(n), Space Complexity: O(1). |
L45. K-th Smallest/Largest Element in BST • take U forward • 221,819 views views
Watch 9 more video solutions →Practice Kth Smallest Element in a BST with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor