Bst

This is a discussion on Bst within the C++ Programming forums, part of the General Programming Boards category; Given a binary search tree with the following declaration: Code: struct node {int value; Node *left, *right;}; class BST{ private: ...

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    133

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

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,747
    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;
      }
    }
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    Actually i just need to pass the root node to function. Dont really have to compare the left and right subtree, right?

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    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.

  5. #5
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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.

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,747
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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.

  8. #8
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,747
    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)
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  9. #9
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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;
     
    }

  10. #10
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,747
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  11. #11
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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
     
    }

  12. #12
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,747
    > rt->left == rt->right == NULL
    This isn't the code I suggested, and this statement doesn't do what you hoped it would do
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  13. #13
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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
     
    }
    
    
     }

  14. #14
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,747
    // 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).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  15. #15
    Registered User
    Join Date
    Sep 2003
    Posts
    133
    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?
    Last edited by Raison; 04-09-2004 at 11:01 AM.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. BST array
    By Iron_Shortage in forum C Programming
    Replies: 5
    Last Post: 04-20-2009, 04:04 PM
  2. bst in postorder to file algorithm?
    By iunah in forum C Programming
    Replies: 2
    Last Post: 02-01-2009, 06:13 AM
  3. problem inserting into recursive BST
    By nfrandsen in forum C Programming
    Replies: 4
    Last Post: 09-13-2008, 08:03 PM
  4. I would love some input on my BST tree.
    By StevenGarcia in forum C++ Programming
    Replies: 4
    Last Post: 01-15-2007, 01:22 AM
  5. Splitting BST General
    By cpp_is_fun in forum C++ Programming
    Replies: 1
    Last Post: 11-25-2005, 02:02 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21