Search Range in Binary Search Tree

Source

LintCode 11

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.

Example

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

    20
   /  \
  8   22
 / \
4   12

Solution

If you know that in-order traversal gives ascending order of the BST, this question should be easy to figure out. To reduce unnecessary search, if current node's value is less than k1 you don't need to keep searching into its left subtree for instance. Note that even if the node's value is less than k1 or greater than k2, you still need to recursively call searchRange() for its right tree and left tree, the example above demonstrate that.

public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
    ArrayList<Integer> result = new ArrayList<>();
    searchRange(root, k1, k2, result);
    return result;
}

public void searchRange(TreeNode node, int k1, int k2, ArrayList<Integer> result) {
    if (node == null) {
        return;
    }

    if (node.val > k1) {
        searchRange(node.left, k1, k2, result);
    }
    if (node.val >= k1 && node.val <= k2) {
        result.add(node.val);
    }
    if (node.val < k2) {
        searchRange(node.right, k1, k2, result);
    }
}