Search Range in Binary Search Tree

[huimeich]

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

[huimeich]

class Solution {
public:
    /**
     * @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.
     */
    vector<int> searchRange(TreeNode* root, int k1, int k2) {
        TreeNode* ll;
        vector<int> res,l,r;
        if (root==NULL) return res;
        if (root->val > k1) res=searchRange(root->left, k1, k2);
        if (root->val >= k1 && root->val <= k2) res.push_back(root->val);
        if (root->val < k2) {
            r=searchRange(root->right,k1, k2);
            res.insert(res.end(),r.begin(),r.end());
        }
    }
};