PROBLEM DESCRIPTION
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.
SOLUTION
APPROACH 1
Store the inorder traversal in a list and return (k-1)th element from the list.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int kthSmallest(TreeNode root, int k) {
return inorder(root, new ArrayList<>()).get(k-1);
}
public List<Integer> inorder(TreeNode root, List<Integer> list){
if(root == null)
return list;
inorder(root.left, list);
list.add(root.val);
inorder(root.right, list);
return list;
}
}
APPROACH 2 (Optimized)
We don’t need to traversal the entire list necessarily. Once we reach the Kth element, we should be returning it. This will be O(k) time complexity.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Solution {
public int kthsmallest(TreeNode A, int B) {
//To store the value of K
int[] k = new int[1];
k[0] = B;
TreeNode n = solve(A, k);
//In case K is more than the number of nodes
if(n != null)
return n.val;
return -1;
}
public TreeNode solve(TreeNode root, int[] k){
if(root == null) return null;
// We do an inorder traversal here.
TreeNode left = solve(root.left, k);
if (k[0] == 0)
return left; // left subtree has k or more elements.
k[0]--;
if(k[0] == 0){
return root; // root is the kth element.
}
return solve(root.right, k); // answer lies in the right node.
}
}