Roger Zhu Roger Zhu - 1 month ago 10
C++ Question

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?

Answer

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 .