LT11 Search Range in Binary Search Tree

Binary search tree

Problem:

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.

If k1 = 10 and k2 = 22, then your function should return [12, 20, 22]

20 / \ 8 22 / \ 4 12

Solution:

• use inorder traversal by recursion, check whether current root's value in the given range.

public void searchRange(TreeNode root, int k1, int k2) {
 if (root == null) return;
 searchRange(root.left, k1, k2);

 if (k1 <= root.val && root.val <= k2) print(root.val);

 searchRange(root.right, k1, k2);
}