LintCod 11 - Search Range in Binary Search Tree

Search Range in Binary Search Tree | Data Structure and Algorithm
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.

For example, if k1 = 10 and k2 = 22, then your function should print 12, 20 and 22.

          20

       /        \

    8           22

  /     \

4       12

Not-Optimized Recursive Version:

    void inorder_dfs(vector<int> &ret, TreeNode *root, int k1, int k2) {
        if (NULL == root) {
            return;
        }

        inorder_dfs(ret, root->left, k1, k2);
        if ((root->val >= k1) && (root->val <= k2)) {
            ret.push_back(root->val);
        }
        inorder_dfs(ret, root->right, k1, k2);
    }

http://www.cnblogs.com/EdwardLiu/p/4391423.html
A little inefficient: Use ArrayList<Integer> res as method argument.

 7     public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {
 8         ArrayList<Integer> res = searchRangeRecur(root,k1,k2);
 9         return res;
10     }
12     public ArrayList<Integer> searchRangeRecur(TreeNode cur, int k1, int k2){
13         ArrayList<Integer> res = new ArrayList<Integer>();
14         if (cur==null) return res;
15         if (k1>k2) return res;
16 
17         ArrayList<Integer> left = searchRangeRecur(cur.left,k1,Math.min(cur.val-1,k2));
18         ArrayList<Integer> right = searchRangeRecur(cur.right,Math.max(cur.val+1,k1),k2);
19 
20         res.addAll(left);
21         if (cur.val>=k1 && cur.val<=k2) res.add(cur.val);
22         res.addAll(right);
23 
24         return res;
25     }

http://blog.welkinlan.com/2015/05/22/search-range-in-binary-search-tree-lintcode-java/
可以优化的地方为「剪枝过程」的处理——不递归遍历不可能有解的节点
Use class variable.
  private ArrayList<Integer> results;

    public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {

        results = new ArrayList<Integer>();

        helper(root, k1, k2);

        return results;

    }

    private void helper(TreeNode root, int k1, int k2) {

        if (root == null) {

            return;

        }

        if (root.val > k1) {

            helper(root.left, k1, k2);

        } // else prune left tree

        if (root.val >= k1 && root.val <= k2) {

            results.add(root.val);

        }

        if (root.val < k2) {

            helper(root.right, k1, k2);

        } // else prune right tree

    }

Iterative in-order traversal:
http://blog.welkinlan.com/2015/05/22/search-range-in-binary-search-tree-lintcode-java/

    public ArrayList<Integer> searchRange(TreeNode root, int k1, int k2) {

        // write your code here

        ArrayList<Integer> result = new ArrayList<Integer>();

        if (root == null) {

            return result;

        }

        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();

        while (root != null || !stack.isEmpty()) {

            //left

            if (root != null) { 

                stack.push(root); // it should also add prune logic here, if root.val < k1, continue, no root=root.left.

                root = root.left;

            } else {

                //root

                root = stack.pop();

                if (root.val >= k1 && root.val <= k2) {

                    result.add(root.val);

                } else if (root.val > k2) { //pruning, optimization

                    break;

                }

                //right

                root = root.right;

            }

        }

        return result;

    }

http://blog.csdn.net/martin_liang/article/details/45771979
Use InorderIterator to encapsulate traversal logic. But better add pruning logic into the iterator.

    BSTIterator(TreeNode *root) {
        TreeNode *pCurNode = root;
        while (pCurNode)
        {
            mStack.push(pCurNode);
            pCurNode = pCurNode->left;
        }
    }
    bool hasNext() {
        if (mStack.size() > 0)
            return true;
        return false;
    }
    int next() {
        TreeNode* retNode = mStack.top();
        mStack.pop();
        
        TreeNode *pCurNode = retNode;
        if (pCurNode->right)
        {
            pCurNode = pCurNode->right;
            while (pCurNode)
            {
                mStack.push(pCurNode);
                pCurNode = pCurNode->left;
            }
        }
        return retNode->val;
    }
};
    vector<int> searchRange(TreeNode* root, int k1, int k2) {
        BSTIterator itr(root);
        vector<int> retVector;
        while (itr.hasNext())
        {
            int curVal = itr.next();
            if (curVal >= k1 && curVal <= k2)
            {
                retVector.push_back(curVal);
            }
        }
        return retVector;
    }

Read full article from Search Range in Binary Search Tree | Data Structure and Algorithm