230. Kth Smallest Element in a BST (Medium)
https://leetcode.com/problems/kth-smallest-element-in-a-bst/
Given a binary search tree, write a function kthSmallest
to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Example 1:
Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Solutions
1.
class Solution {
// Traverse the binary search tree by non-recursive way.
public int kthSmallest(TreeNode root, int k) {
Stack<TreeNode> stack = new Stack<>();
TreeNode p = root;
stack.push(p);
// using loop instead of recursion
while (!stack.isEmpty() || p != null) {
// visit left until no child
if (p != null) {
stack.push(p);
p = p.left;
continue;
}
// p = null && stack not empty
// visit stack top
TreeNode t = stack.pop();
k--;
if (k == 0) {
return t.val;
}
p = t.right; // visit right
}
// never reached
return -1;
}
}
2.
class Solution {
// Traverse the binary search tree by recursive way.
public int kthSmallest(TreeNode root, int k) {
Stack<Integer> track = new Stack<>();
recurse(root, k, track);
return track.pop();
}
public int recurse(TreeNode root, int k, Stack<Integer> track) {
// This should be placed at the head of function since priority of return 1
// weighs much more than return 0. return 1 means all the recursion
// searching should ceased immediately.
if (track.size() == k) {
// already find the target value, break down searching task
return 1;
}
if (root == null) {
return 0;
}
int rst = recurse(root.left, k, track);
if (rst == 1) { // break down searching
return rst;
}
track.push(root.val);
rst = recurse(root.right, k, track);
return rst;
}
}
Incorrect Solutions
References
https://www.programcreek.com/2014/07/leetcode-kth-smallest-element-in-a-bst-java/