Thread: Bst

Given a binary search tree with the following declaration:

Code:

struct node
{int value;
  Node *left, *right;};

class BST{
private: 
Node *head;

public:
BST(){head = NuLL;}
};

I need to find all the shortest paths in the tree. For example:

10
/ \
6 15
/ \ \
2 7 12

I should print:
10 6 2
10 6 7
10 15 12

I am allowed to make use of data structures of list, stack and queue together with their basic manipulation functions.

Can someone give me an idea on how should i start(don't need codes)? I believe i need to find the min ht of the tree first, but i dont even know how to do that.

Second Question:
How is a function to find the max ht of a BST typically written? I thought of one way and i need someone to tell me if there's a better way

Code:

//pass the root of a non empty tree to this node
// the functions returns the max ht through maxHt
void BST::findMaxHt(node *rt,int curHt=0, int &maxHt)
{
   if(rt==NULL) return;

  if(curHt>maxHt)
  maxHt= curHt;

  findMaxHt(rt->left, curHt+1, maxHt);
  findMaxtHt(rt->right, curHt+1, maxHt);
}

Actually i just need to pass the root node to function. Dont really have to compare the left and right subtree, right?

The initial node evaluated in Salems function will be the root node of the entire tree. However, note that findMaxHt() as posted is recursive. That is, within each call to findMaxHt() there will be two further calls to findMaxHt() (one for left subtree of current node and one for righ subtree of current node) or none, if current node is a leaf. In effect, with each call to findMaxHt() the current node acts as the root node for its own subtree.

OK I understand now for the max ht. Thanks alot!

So does anyone know how to solve the first question? I been thinking about it for very long. And i cant think of a way to find the min ht of the tree, which probably need the use of a queue ADT.

Originally Posted by Salem

Well first you find the min height, using the examples provided above

Then pass that min height to another function which walks the tree. If you reach a leaf node and your path is the same length as the min height, then print it.

Can u give me an rough idea on how to find the min ht and what to do after that?

Cos i figured it out even if i know the min ht. I need to find a way to start traversing from the root to print each shortest path, which i dont know how too.

Consolidating from all the valuable help i got, here is what i came up with. So did i get it right?

Code:

int BST::findMinHt(node *rt)
{
  if(rt==NULL) return 0;

  // height of left and right sub-trees
  int l = findMaxHt(rt->left);
  int r = findMaxtHt(rt->right);

  // return the max
  if ( l < r ) {
    return l + 1;
  } else {
    return r + 1;
  }
}


void BST::shortestPath(node *rt,stack &s,int minHt)
{
   if(minHt==0)
   {s.print(); // print the value of the nodes when minHt is reached
    return;}
   
   stack.push(rt); // store node during pre-traversal
   shortestPath(rt->left,s, minHt-1);
   shortestPath(rt->right,s, minHt-1);
   stack.pop(); // remove node during post-treversal
 
}

void stack::print()
{
   node *cur = head;
    
    while(cur)
    {cout << cur->value << ' ';
     cur = cur->nextPtr;   
    }
    
    cout<<endl;
 
}

Take the following tree as example:

Clearly, the min ht of the tree is at 12 and it is the only shortest path. But i will reach the left child of 6 (which is an empty node) first before reaching the path to 12 and they are at the same ht.

SO i should CHECK for the node to be a leaf node and is at min ht.
I amended the code. Correct me if i am wrong. Thanks.

Code:

   10
   / \ 
  6   15
   \    \
    7   12
   /
 4


void BST::shortestPath(node *rt,stack &s,int minHt)
{ 
  if(rt == NULL)
  return;
 
   stack.push(rt); // store node during pre-traversal

   // check for whether min ht is reached and the last node is a leaf
   if( (minHt==0) && (rt->left == rt->right == NULL))
   {s.print(); // print the value of the nodes 
    return;}

   shortestPath(rt->left,s, minHt-1);
   shortestPath(rt->right,s, minHt-1);
   stack.pop(); // remove node during post-treversal
 
}

Salem,
Sorry i am a slow learner and very confused at the moment.
Hope u have the patience.
Regarding the code u recommended, i believe it look like this:

Code:

void BST::shortestPath(node *rt,stack &s,int minHt)
{ 
//--------What u suggested-------------// 
 if ( rt == NULL ) 
 {
  if ( minHt==0 ) 
  { s.print();}
  return; 
 }
//------------------------------------------//

   stack.push(rt); // store node during pre-traversal

   
   shortestPath(rt->left,s, minHt-1);
   shortestPath(rt->right,s, minHt-1);
   stack.pop(); // remove node during post-treversal
 
}

}

I am not too sure how it works. "rt" will only be NULL when minHt = -1 . This way will never print the path out, right? I'm thinking perhaps we use this instead:

Code:

void BST::shortestPath(node *rt,stack &s,int minHt)
{ 
   // the transversing may reach an empty node before
   // reaching minHt==0
   if(rt==NULL)
   {return;}

   stack.push(rt); // store node during pre-traversal 
  
  // check for leaf and minHt reached
   if(minHt == 0 && rt->left ==NULL && rt->right == NULL )
   { s.print();
     return;}

   shortestPath(rt->left,s, minHt-1);
   shortestPath(rt->right,s, minHt-1);
   stack.pop(); // remove node during post-treversal
 
}


 }