doubling tree

This is a discussion on doubling tree within the C++ Programming forums, part of the General Programming Boards category; Hi, I would really appreciate any help on this. Doubling tree is a problem where a duplicate node is inserted ...

  1. #1
    Registered User
    Join Date
    Mar 2008
    Posts
    10

    Unhappy doubling tree

    Hi,
    I would really appreciate any help on this.

    Doubling tree is a problem where a duplicate node is inserted as a left child for each node in a binary search tree.

    This code works:
    Code:
    void doubleTree(root)
    {
    if(root == NULL) return;
    else
    {
    doubleTree(root->LeftChild);
    doubleTree(root->RightChild);
    
    ...
    .....
    <create a new node and insert as the left child with data field of the node same as node>
    }
    }
    but this doesnt: ????????
    Code:
    void doubleTree(root)
    {
    if(root == NULL) return;
    else
        {
        ...
        ..... 
        <create a new node and insert as the left child with data field of the node      
        same as node>
    
        doubleTree(root->LeftChild);
        doubleTree(root->RightChild);
    
        }
    }
    Shouldnt it work??

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,299
    Nope. You'd get stack overflow because root->LeftChild is the node you just inserted, so you'd keep infinitely recursing to the node you just inserted.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Mar 2008
    Posts
    10
    thnks a lot for the explanation.

    one more doubt...does recursion in a binary search tree lead to top-bottom or bottom - top traversal, or can it be both ??

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    That's kind of an odd follow-up question. Is this for homework?

    The fact that you don't know the answer shows that you don't understand recursion, or traversal of binary trees... I'm not sure that just giving you answers is going to help you any.

  5. #5
    Registered User
    Join Date
    Mar 2008
    Posts
    10
    Quote Originally Posted by gunner4life View Post
    Hi,
    I would really appreciate any help on this.

    Doubling tree is a problem where a duplicate node is inserted as a left child for each node in a binary search tree.

    This code works:
    Code:
    void doubleTree(root)
    {
    if(root == NULL) return;
    else
    {
    doubleTree(root->LeftChild);
    doubleTree(root->RightChild);
    
    ...
    .....
    <create a new node and insert as the left child with data field of the node same as node>
    }
    }
    but this doesnt: ????????
    Code:
    void doubleTree(root)
    {
    if(root == NULL) return;
    else
        {
        ...
        ..... 
        <create a new node and insert as the left child with data field of the node      
        same as node>
    
        doubleTree(root->LeftChild);
        doubleTree(root->RightChild);
    
        }
    }
    Shouldnt it work??
    sry consider me noob....but i wanted to ask

    Is the order of insertion in the above case top-bottom?? its evident that the tree traversal is top-bottom...

  6. #6
    Registered User
    Join Date
    Mar 2008
    Posts
    10
    bounce!!!!

  7. #7
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    I think the phrase you're looking for is "bump" and hey, don't do it.
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Tree Search
    By C++Newbie in forum C++ Programming
    Replies: 7
    Last Post: 04-05-2011, 01:17 AM
  2. Interpreter.c
    By moussa in forum C Programming
    Replies: 4
    Last Post: 05-28-2008, 05:59 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 10:45 PM

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