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.
Example
For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.
20
/ \
8 22
/ \
4 12
public class Solution { /** * @param root: The root of the binary search tree. * @param k1 and k2: range k1 to k2. * @return: Return all keys that k1<=key<=k2 in ascending order. */ public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) { // write your code here ArrayList<Integer> list = new ArrayList<Integer>(); if(root == null) return list; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode runner = root; while(runner != null || !stack.isEmpty()){ if(runner != null){ stack.push(runner); runner = runner.left; } else{ runner = stack.pop(); if(k1<= runner.val && k2>= runner.val){ list.add(runner.val); } runner = runner.right; } } return list; } } public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) { // write your code here ArrayList<Integer> list = searchRangeRecursion(root,k1,k2); return list; } public ArrayList<Integer> searchRangeRecursion(TreeNode root, int k1, int k2){ ArrayList<Integer> list = new ArrayList<Integer>(); if(root == null) return list; if(k1 > k2) return list; ArrayList<Integer> left = searchRangeRecursion(root.left,k1,Math.min(root.val-1,k2)); ArrayList<Integer> right = searchRangeRecursion(root.right,Math.max(k1,root.val+1),k2); list.addAll(left); if(k1<= root.val && k2>= root.val){ list.add(root.val); } list.addAll(right); return list; }