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);
}

Well you need to compare the left and right heights at each node, and return the min

Code:

int BST::findMaxHt(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;
  }
}

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.

> So does anyone know how to solve the first question?
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.

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.

I've already pasted max height, just change > to < in my previous code and you're done

Plus I've already shown you tree traversal.
Use the queue idea to maintain a list of visited nodes (recursive calls add to the list, recursive returns remove from the list)

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;
 
}

> if(minHt==0)
Close!
I think you want

Code:

if ( rt == NULL ) {
  if ( minHt==0 ) {
    s.print();
  }
  return;
}

You always return when you reach a leaf (rt==NULL)
If at the same time, minHt is also 0, then you've also found a shortest path as well, so print it.

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
 
}

> rt->left == rt->right == NULL
This isn't the code I suggested, and this statement doesn't do what you hoped it would do

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
 
}


 }

// the transversing may reach an empty node before
// reaching minHt==0
Not if you're printing the shortest path it can't

If it is a shortest path, then minHt == 0 when rt == NULL
If it is a long path, then minHt reaches 0 before rt becomes NULL. At this point, you can stop the recursion (because nothing below this node can be a shortest path either).

Code:

      10
      / \ 
     6   15
      \    \
       7   12
      /     \
     4      30

The min ht of this tree is 3. The left child of 6 is an empty node is at ht 1. Since we transverse left first, we reach the empty left child of 6 before reaching the min ht. We will end pushing an empty node and the program will try to transverse further.

Am i seeing things the wrong way?