Roger Zhu - 2 months ago 13

C++ Question

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 :

- Do inorder traversal of the BST.
- Start from the root.
- Process left subtree for inorder traversal only if the root of left subtree is smaller than 'lowValue'
- Process right subtree only if root of right subtree is greater than 'highValue'
Else just return from the function.

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