Print BST keys in the given range | GeeksforGeeks

Print BST keys in the given range | GeeksforGeeks
Given two values k1 and k2 (where k1 < k2) and a root pointer to a Binary Search Tree. Print 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. Print all the keys in increasing order.

1) If value of root’s key is greater than k1, then recursively call in left subtree.
2) If value of root’s key is in range, then print the root’s key.
3) If value of root’s key is smaller than k2, then recursively call in right subtree.

void Print(struct node *root, int k1, int k2)

{

   /* base case */

   if ( NULL == root )

      return;

   /* Since the desired o/p is sorted, recurse for left subtree first

      If root->data is greater than k1, then only we can get o/p keys

      in left subtree */

   if ( k1 < root->data )

     Print(root->left, k1, k2);

   /* if root's data lies in range, then prints root's data */

   if ( k1 <= root->data && k2 >= root->data )

     printf("%d ", root->data );

  /* If root->data is smaller than k2, then only we can get o/p keys

      in right subtree */

   if ( k2 > root->data )

     Print(root->right, k1, k2);

}

http://likemyblogger.blogspot.com/2015/08/mj-12-print-bst-keys-in-given-range.html

    vector<int> getKeys(TreeNode *root, int lb, int ub){

        vector<int> ret;

        helper(root, lb, ub, ret);

        PrintVector(ret, "ret");

        return ret;

    }

    void helper(TreeNode *root, int lb, int ub, vector<int> &ret){

        if(!root) return;

        if(root->val>=lb && root->val<=ub){

            ret.push_back(root->val);

            helper(root->left, lb, ub, ret);

            helper(root->right, lb, ub, ret);

        }else if(root->val<lb){

            helper(root->right, lb, ub, ret);

        }else{

            helper(root->left, lb, ub, ret);

        }

    }

Read full article from Print BST keys in the given range | GeeksforGeeks