10 Replies Latest reply: Mar 31, 2010 7:16 AM by 807580 RSS

    Merging two binary trees

    807580
      Hi fellow programmers here, i have a question:

      let say user input 2 binary tree

      Tree1
               1
         2         3
      4    5    6   7
      Tree2
                8
         9          10
      11 12   13   14
      how to combine them to make it look like this:

      newTree
                        - (empty root)
                1                                8
            2      3                          9       10
         4    5   6   7                     11  12  13  14
      where Tree1 and Tree2 is the left and right child of newTree.

      Your help is appreciated
        • 1. Re: Merging two binary trees
          807580
          Something like:
          TreeNode newRoot = new TreeNode();
          newRoot.setLeftNode(tree1Root);
          newRoot.setRightNode(tree2Root);
          ?

          Edit: And no, that is not valid Java code. It is pseudocode.
          • 2. Re: Merging two binary trees
            807580
            Yes, the pseudocode is like that.

            Any idea on how to implement it?

            Your help is appreciated
            • 3. Re: Merging two binary trees
              800268
              The same way you implemented Tree1 and Tree2?
              • 4. Re: Merging two binary trees
                791266
                NgSG wrote:
                Yes, the pseudocode is like that.

                Any idea on how to implement it?

                Your help is appreciated
                Are you implementing the whole tree structure, or are you using some library that already exist?

                Kaj
                • 5. Re: Merging two binary trees
                  807580
                  Hi kajbj, i planning to implement the whole tree structure. Doesn't know of any library.

                  Your help is appreciated.

                  Hi Walterlaan, i don't think is that way, as i am inserting integers into tree1 and tree2, but for newTree, it is an Tree itself with integers, so i am not sure.

                  Edited by: NgSG on Mar 24, 2010 9:49 PM
                  • 6. Re: Merging two binary trees
                    791266
                    A node has a left child and a right child, and an optional value attached to it. Note that a Tree is just a Node with populated children.

                    Does that help?
                    • 7. Re: Merging two binary trees
                      807580
                      Ok. The code below is an BST insert example.
                      public void insert(int id) {
                              Node newNode = new Node();    // make new node
                              newNode.num = id;           // insert data
                              if (root == null) // no node in root
                              {
                                  root = newNode;
                              } else // root occupied
                              {
                                  Node current = root;       // start at root
                                  Node parent;
                                  while (true) // (exits internally)
                                  {
                                      parent = current;
                                      if (id < current.num) // go left?
                                      {
                                          current = current.leftChild;
                                          if (current == null) // if end of the line,
                                          {                 // insert on left
                                              parent.leftChild = newNode;
                                              return;
                                          }
                                      } // end if go left
                                      else // or go right?
                                      {
                                          current = current.rightChild;
                                          if (current == null) // if end of the line
                                          {                 // insert on right
                                              parent.rightChild = newNode;
                                              return;
                                          }
                                      }  // end else go right
                                  }  // end while
                              }  // end else not root
                          }  // end insert()
                      I am assuming the code to merge the two trees should be some adjustment to the above code.

                      Thus i wonder,
                      For the argument for insert method, should my argument continue to be an integer or should be an Node or even a Tree?

                      Also, since you mention that a Tree is just a Node with populated children, isit possible for me to extract just the root of Tree1 and Tree2 and the rest of its children will be attached with it?

                      More help is appreciated.
                      • 8. Re: Merging two binary trees
                        807580
                        I think i have finally know how to do it after trial and error, thanks for the input!

                        My own code can work now!
                        • 9. Re: Merging two binary trees
                          791266
                          NgSG wrote:
                          }  // end else go right
                          }  // end while
                          }  // end else not root
                          }  // end insert()
                          Just a side note. Feeling that you need to comment the closing curly brackets usually indicate that your method is either too long, or has too complex logic. The solution to that is usually to rewrite the logic, or break it down into several shorter methods with descriptive method names, and arguments.

                          Kaj
                          • 10. Re: Merging two binary trees
                            807580
                            Hi, may I know how you do the merging?

                            -)