Problem Statement:
Given the root of a binary search tree, and an integer k, return the th smallest value (1-indexed) of all the values of the nodes in the tree.
Examples:
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
Example 3:
Input: root = [4,2,7,1,3,null,null,null,null,null,null], val = 5
Output: [4,2,7,1,3,5]
Constraints:
- The number of nodes in the tree is
n. 1 <= k <= n <= 1040 <= Node.val <= 104
Approach
- In-order Traversal of BST gives sorted order of elements.
- Use a counter
count = kto track how many elements we’ve visited. - Traverse left subtree, decrement
count. - When
count === 0, current node is the kth smallest → store it inans. - Stop traversal once we find the answer.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(h)(h=tree height)
Dry Run
Function Call: kthSmallest(root, 3) where
root = Node(5)
├── left: Node(3)
│ ├── left: Node(2)
│ │ └── left: Node(1)
│ └── right: Node(4)
└── right: Node(7)
├── left: Node(6)
└── right: Node(8)
Initial State:
→ ans = null
→ count = 3
Step 1:
→ traversal(curr = 5)
→ curr.left exists → traversal(curr = 3)
Step 2:
→ traversal(curr = 3)
→ curr.left exists → traversal(curr = 2)
Step 3:
→ traversal(curr = 2)
→ curr.left exists → traversal(curr = 1)
Step 4:
→ traversal(curr = 1)
→ curr.left is null → skip
→ –count → count = 2
→ count ≠ 0 → skip setting ans
→ curr.right is null → skip
→ return
Step 5:
→ Back to traversal(curr = 2)
→ –count → count = 1
→ count ≠ 0 → skip setting ans
→ curr.right is null → skip
→ return
Step 6:
→ Back to traversal(curr = 3)
→ –count → count = 0
→ count == 0 → ans = 3
→ curr.right = Node(4), but ans is already found → return
Final Result: ans = 3 → the 3rd smallest element in the BST
root = Node(5)
├── left: Node(3)
│ ├── left: Node(2)
│ │ └── left: Node(1)
│ └── right: Node(4)
└── right: Node(7)
├── left: Node(6)
└── right: Node(8)
Initial State:
→ ans = null
→ count = 3
Step 1:
→ traversal(curr = 5)
→ curr.left exists → traversal(curr = 3)
Step 2:
→ traversal(curr = 3)
→ curr.left exists → traversal(curr = 2)
Step 3:
→ traversal(curr = 2)
→ curr.left exists → traversal(curr = 1)
Step 4:
→ traversal(curr = 1)
→ curr.left is null → skip
→ –count → count = 2
→ count ≠ 0 → skip setting ans
→ curr.right is null → skip
→ return
Step 5:
→ Back to traversal(curr = 2)
→ –count → count = 1
→ count ≠ 0 → skip setting ans
→ curr.right is null → skip
→ return
Step 6:
→ Back to traversal(curr = 3)
→ –count → count = 0
→ count == 0 → ans = 3
→ curr.right = Node(4), but ans is already found → return
Final Result: ans = 3 → the 3rd smallest element in the BST
var kthSmallest = function(root, k) {
let ans = null;
let count = k;
let traversal = (curr) => {
if(ans != null) return;
curr.left && traversal(curr.left);
--count;
if(count == 0){
ans = curr.val;
}
curr.right && traversal(curr.right);
}
traversal(root);
return ans;
};
class Solution:
def kthSmallest(self, root, k):
self.count = k
self.ans = None
def inorder(node):
if not node or self.ans is not None:
return
inorder(node.left)
self.count -= 1
if self.count == 0:
self.ans = node.val
return
inorder(node.right)
inorder(root)
return self.ans
class Solution {
private int count;
private int result;
public int kthSmallest(TreeNode root, int k) {
count = k;
inorder(root);
return result;
}
private void inorder(TreeNode node) {
if (node == null || count == 0) return;
inorder(node.left);
count--;
if (count == 0) {
result = node.val;
return;
}
inorder(node.right);
}
}
class Solution {
public:
int count;
int ans;
void inorder(TreeNode* root) {
if (!root || count == 0) return;
inorder(root->left);
count--;
if (count == 0) {
ans = root->val;
return;
}
inorder(root->right);
}
int kthSmallest(TreeNode* root, int k) {
count = k;
inorder(root);
return ans;
}
};
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
void inorder(struct TreeNode* root, int* count, int* result) {
if (!root || *result != -1) return;
inorder(root->left, count, result);
(*count)--;
if (*count == 0) {
*result = root->val;
return;
}
inorder(root->right, count, result);
}
int kthSmallest(struct TreeNode* root, int k) {
int result = -1;
inorder(root, &k, &result);
return result;
}
public class Solution {
private int count;
private int result;
public int KthSmallest(TreeNode root, int k) {
count = k;
InOrder(root);
return result;
}
private void InOrder(TreeNode node) {
if (node == null || count == 0) return;
InOrder(node.left);
count--;
if (count == 0) {
result = node.val;
return;
}
InOrder(node.right);
}
}
