Kth Smallest Element in a BST
MedPrompt
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: 1Example 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 <= 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?
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses inorder traversal to store all elements in an array and then returns the kth element.
Algorithm
- Create a list to store elements
- Perform inorder traversal:
- Recursively traverse left subtree
- Add current node value to list
- Recursively traverse right subtree
- Return the (k-1)th element from the list
Walkthrough
In this approach, we perform an inorder traversal of the BST and store all elements in an array. Since inorder traversal of a BST visits nodes in ascending order, we can simply return the (k-1)th element from the array.
class Solution { List<Integer> inorderList = new ArrayList<>(); public int kthSmallest(TreeNode root, int k) { inorderTraversal(root); return inorderList.get(k-1); } private void inorderTraversal(TreeNode node) { if (node == null) return; inorderTraversal(node.left); inorderList.add(node.val); inorderTraversal(node.right); }}Complexity
Time
O(n) where n is the number of nodes in the tree
Space
O(n) to store all elements in the array
Trade-offs
Pros
Simple to implement
Easy to understand
Can be used when k is not known beforehand
Cons
Uses extra space to store all elements
Processes all nodes even when k is small
Not efficient for large trees when k is small
This approach uses iterative inorder traversal with a counter to stop when kth element is found.
Algorithm
- Initialize a stack and current pointer to root
- While current is not null or stack is not empty:
- Push all left nodes to stack
- Pop node from stack
- Increment counter
- If counter equals k, return node value
- Move to right child
Walkthrough
We perform an iterative inorder traversal using a stack. We maintain a counter and stop as soon as we find the kth element, avoiding unnecessary traversal of remaining nodes.
class Solution { public int kthSmallest(TreeNode root, int k) { Stack<TreeNode> stack = new Stack<>(); TreeNode curr = root; int count = 0; while (curr != null || !stack.isEmpty()) { while (curr != null) { stack.push(curr); curr = curr.left; } curr = stack.pop(); count++; if (count == k) { return curr.val; } curr = curr.right; } return -1; }}Complexity
Time
O(H + k) where H is the height of tree
Space
O(H) where H is the height of tree
Trade-offs
Pros
More efficient than storing all elements
Stops as soon as kth element is found
Uses less memory than storing all elements
Cons
More complex implementation than recursive approach
Still requires stack space
For the follow-up question where BST is modified frequently, we can augment the BST node with count of left subtree nodes.
Algorithm
- Augment TreeNode with leftCount
- While traversing:
- If leftCount + 1 equals k, return current value
- If leftCount >= k, go left
- Otherwise, subtract leftCount + 1 from k and go right
Walkthrough
We modify the TreeNode class to include a count of nodes in the left subtree. This helps in determining the position of current node quickly.
class TreeNode { int val; int leftCount; // count of nodes in left subtree TreeNode left; TreeNode right; TreeNode(int val) { this.val = val; this.leftCount = 0; }} class Solution { public int kthSmallest(TreeNode root, int k) { TreeNode curr = root; while (curr != null) { if (curr.leftCount + 1 == k) { return curr.val; } else if (curr.leftCount >= k) { curr = curr.left; } else { k = k - (curr.leftCount + 1); curr = curr.right; } } return -1; }}Complexity
Time
O(H) where H is the height of tree
Space
O(1) for queries (O(n) for maintaining counts in nodes)
Trade-offs
Pros
O(H) time complexity for queries
Efficient for frequent queries
No extra space needed during query
Optimal for dynamic BST with frequent kth smallest queries
Cons
Requires modification to tree structure
Need to maintain leftCount during insertions and deletions
More complex implementation for tree modifications
Solutions
Solution
import java.util.Comparator ; import java.util.PriorityQueue ; public class Kth_Smallest_Element_in_a_BST { /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { PriorityQueue < Integer > heap = new PriorityQueue <>( new Comparator < Integer >() { @Override public int compare ( Integer o1 , Integer o2 ) { return o2 - o1 ; } }); public int kthSmallest ( TreeNode root , int k ) { dfs ( root , k ); return heap . peek (); } private void dfs ( TreeNode root , int k ) { if ( root == null ) { return ; } // maintain heap if ( heap . size () < k ) { heap . offer ( root . val ); // followup question, heap.remove() is by object, not index. // so if delete operation, just remove element from both tree and heap } else { int val = root . val ; if ( val < heap . peek ()) { heap . poll (); heap . offer ( val ); } } dfs ( root . left , k ); dfs ( root . right , k ); } } } class Solution_followUp { public int kthSmallest ( TreeNode root , int k ) { MyTreeNode node = build ( root ); return dfs ( node , k ); } class MyTreeNode { int val ; int count ; // key point to add up and find k-th element MyTreeNode left ; MyTreeNode right ; MyTreeNode ( int x ) { this . val = x ; this . count = 1 ; } }; MyTreeNode build ( TreeNode root ) { if ( root == null ) return null ; MyTreeNode node = new MyTreeNode ( root . val ); node . left = build ( root . left ); node . right = build ( root . right ); if ( node . left != null ) node . count += node . left . count ; if ( node . right != null ) node . count += node . right . count ; return node ; } int dfs ( MyTreeNode node , int k ) { if ( node . left != null ) { int cnt = node . left . count ; if ( k <= cnt ) { return dfs ( node . left , k ); } else if ( k > cnt + 1 ) { return dfs ( node . right , k - 1 - cnt ); // -1 is to exclude current root } else { // k == cnt + 1 return node . val ; } } else { if ( k == 1 ) return node . val ; return dfs ( node . right , k - 1 ); } } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int kthSmallest ( TreeNode root , int k ) { Deque < TreeNode > stk = new ArrayDeque <>(); while ( root != null || ! stk . isEmpty ()) { if ( root != null ) { stk . push ( root ); root = root . left ; } else { root = stk . pop (); if (-- k == 0 ) { return root . val ; } root = root . right ; } } return 0 ; } }# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution : def kthSmallest ( self , root : Optional [ TreeNode ], k : int ) -> int : stk = [] while root or stk : if root : stk . append ( root ) root = root . left else : root = stk . pop () k -= 1 if k == 0 : return root . val root = root . right ############ # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution_followUp : def kthSmallest ( self , root : TreeNode , k : int ) -> int : node = self . build ( root ) return self . dfs ( node , k ) class MyTreeNode : def __init__ ( self , x ): self . val = x self . count = 1 # default 1 self . left = None self . right = None def build ( self , root : TreeNode ) -> MyTreeNode : if not root : return None node = self . MyTreeNode ( root . val ) # default count already is 1 node . left = self . build ( root . left ) node . right = self . build ( root . right ) if node . left : node . count += node . left . count if node . right : node . count += node . right . count return node def dfs ( self , node : MyTreeNode , k : int ) -> int : if node . left : cnt = node . left . count if k < cnt + 1 : return self . dfs ( node . left , k ) elif k > cnt + 1 : return self . dfs ( node . right , k - 1 - cnt ) else : # k == cnt+1 return node . val else : if k == 1 : # cannot move to beginning of dfs() return node . val return self . dfs ( node . right , k - 1 )// OJ: https://leetcode.com/problems/kth-smallest-element-in-a-bst/ // Time: O(N) // Space: O(H) class Solution { public: int kthSmallest ( TreeNode * root , int k ) { function < int ( TreeNode * ) > inorder = [ & ]( TreeNode * root ) { if ( ! root ) return - 1 ; int val = inorder ( root -> left ); if ( val != - 1 ) return val ; if ( -- k == 0 ) return root -> val ; return inorder ( root -> right ); }; return inorder ( root ); } };Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.