# Bst

Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last
• 04-08-2004
Raison
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); }```
• 04-08-2004
Salem
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;   } }```
• 04-08-2004
Raison
Actually i just need to pass the root node to function. Dont really have to compare the left and right subtree, right?
• 04-08-2004
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.
• 04-08-2004
Raison
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.
• 04-09-2004
Salem
> 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.
• 04-09-2004
Raison
Quote:

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.
• 04-09-2004
Salem
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)
• 04-09-2004
Raison
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;   }```
• 04-09-2004
Salem
> 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.
• 04-09-2004
Raison
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   }```
• 04-09-2004
Salem
> rt->left == rt->right == NULL
This isn't the code I suggested, and this statement doesn't do what you hoped it would do
• 04-09-2004
Raison
Salem,
Sorry i am a slow learner and very confused at the moment.
Hope u have the patience. :p
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   }  }```
• 04-09-2004
Salem
// 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).
• 04-09-2004
Raison
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?
Show 80 post(s) from this thread on one page
Page 1 of 2 12 Last