CODEWITHSUNDEEP
c++searchbinary-search-tree
Roger Zhu
Roger Zhu

Reputation: 75

How to print the numbers bewteen a specific range in BST from highest to lowest with least nodes visited?

For a BST, I want to find the nodes' values in [a,b] form largerest value to smallest one. The simplest way I can think is as follows:

void printRange(BSTNode<Key,E>* root,int lowValue,int highValue) const
{
    if(root==NULL) return;

    printRange(root->right(),lowValue,highValue);
    if(root->key()>=lowValue&&root->key()<=highValue)
        cout<<root->key()<<" ";

    printRange(root->left(),lowValue,highValue);
}

But I want to know whether there is a way to print out these values with less nodes visited?

Upvotes: 0

Views: 1973

Answers (2)

AndrewGrant
AndrewGrant

Reputation: 808

The answer to this question, is psuedo code, should have been this:

void printRange(int lower, int upper, BSTNode * node){
  if (node == NULL) return
  if (node->key <= upper) printRange(lower, upper, node->right);
  if (node->key >= lower && node->key <= upper) printf("%d",node->value);
  if (node->key >= lower) printRange(lower, upper, node->left);
}

Upvotes: 1

DhruvPathak
DhruvPathak

Reputation: 43245

You are visiting all the nodes of the BST , irrespective of whether they lie in the range or not. And printing only the required values. A more refined algorithm would be :

  1. Do inorder traversal of the BST.

  2. Start from the root.

  3. Process left subtree for inorder traversal only if the root of left subtree is smaller than 'lowValue'

  4. Process right subtree only if root of right subtree is greater than 'highValue'

  5. Else just return from the function.

    This way you do a filtered inorder traversal,visiting only the required part of your BST .

Upvotes: 1

Related Questions