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?
Problem Overview: Given the root of a Binary Search Tree (BST) and an integer k, return the kth smallest value among all nodes. The key observation is that an in-order traversal of a BST visits nodes in strictly increasing order.
The BST property makes this problem straightforward once you recognize the traversal order. In-order traversal processes nodes as left → root → right, which naturally produces a sorted sequence. Instead of storing the entire sequence, you only need to count nodes until the kth element appears.
Approach 1: In-Order Traversal (Recursive) (O(n) time, O(h) space)
This approach performs a standard in-order traversal of the tree. Maintain a counter that increments every time you visit a node. Once the counter equals k, return that node’s value immediately. Because a BST guarantees sorted order during in-order traversal, the kth visited node is the kth smallest element.
The recursion stack holds at most h nodes where h is the tree height. In a balanced tree this is O(log n), but in the worst case (skewed tree) it becomes O(n). This solution is simple, easy to reason about, and commonly expected in interviews involving tree traversal or depth-first search.
Approach 2: Morris In-Order Traversal (Iterative) (O(n) time, O(1) space)
Morris Traversal performs in-order traversal without recursion or an explicit stack. It temporarily modifies the tree by creating threaded links from a node’s predecessor back to the current node. This allows traversal to return to parent nodes without storing them in memory.
During traversal, increment a counter each time a node is processed. When the counter reaches k, return the current value. After visiting a node, restore the modified pointers so the tree structure remains unchanged. This method achieves constant extra space while still visiting each node at most twice.
Morris traversal is especially useful when memory usage must stay minimal. It’s less commonly written in interviews but demonstrates strong understanding of binary search tree traversal mechanics.
Recommended for interviews: The recursive in-order traversal is the expected answer in most interviews because it directly uses the BST ordering property and is easy to implement quickly. Mentioning Morris traversal as a follow-up shows deeper knowledge of tree traversal optimizations and space reduction techniques.
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.
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.
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). |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-Order Traversal (Recursive) | O(n) | O(h) | General interview solution; simple and leverages BST ordering |
| Morris In-Order Traversal | O(n) | O(1) | When minimizing extra memory or demonstrating advanced traversal techniques |
Kth Smallest Element in a BST - Leetcode 230 - Python • NeetCode • 255,013 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 FleetCode