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
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 ; } }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.