Search Range in Binary Search Tree
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Find all the keys of tree in range k1 to k2. i.e. print all x such that k1<=x<=k2 and x is a key of given BST. Return all the keys in ascending order.
Solution:
In-order traversal of binary search tree is in ascending order.
Code:
public class Solution {
public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
ArrayList<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while (cur != null || !stack.empty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
if (k1 <= cur.val && cur.val <= k2) {
res.add(cur.val);
}
cur = cur.right;
}
return res;
}
}