Solved

binary trees

Posted on 2004-10-10
7
343 Views
Last Modified: 2010-03-31
Hi,

If I have 2 binary trees that are sorted (meaning the left subtree contains nodes smaller that it's parent, while the right subtree contains larger nodes). Let's say the nodes contain an integer.
How would I write a function to merge the two trees?

The way I was thinking was
1) traverse one of the trees using in-order traversal (meaning left node, then root node, then right node)
2) For each node in this tree, I would call an insert method that would insert this node into the other tree.

I guess this would work but is there are better way? Would it be possible somehow to insert more than 1 node at a time (because the tree being traversed is also sorted)?

Any ideas to accomplish this using a good algorithm would be appreciated.

Thanks
AJ
0
Comment
Question by:aj_2003
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
7 Comments
 
LVL 92

Expert Comment

by:objects
ID: 12273440
you should just be able to insert the root node of one tree into the other.
0
 
LVL 21

Expert Comment

by:MogalManic
ID: 12275135
Maybe the algorithm should rebalance the tree as well as merge
 1) Compute median of tree 1 & tree 2
 2) Traverse each tree starting at each median
 3) Build new tree as you traverse each tree
 4) When you reach a leaf node of one tree, the subtree of the other tree can be inserted on that leaf.
 
0
 

Author Comment

by:aj_2003
ID: 12279090
Object,
You can't do that.

Eg:

     5      
  /    \
1      10

     4
  /    \
1       6

First of all you could 2 nodes with the same integer.
Secondly, based on the comparison of the 2 root nodes, we would place the 2nd tree in the left side of the 5 of tree 1. But this would be wrong since the 6 is larger than the 5.

MogalManic,

When you say find median, how would you do that? But let's say you find it. Then it doesn't necessary have to be at the root node of a tree. This means you have already traversed down the tree. So how are you supposed to go back up the tree and traverse the left side of the root node - we dont have up pointers. Unless I am misunderstanding you, I am not sure how that would work. Can you give me a code example.

0
Salesforce Has Never Been Easier

Improve and reinforce salesforce training & adoption using WalkMe's digital adoption platform. Start saving on costly employee training by creating fast intuitive Walk-Thrus for Salesforce. Claim your Free Account Now

 
LVL 24

Expert Comment

by:sciuriware
ID: 12284237
I'm afraid the only way to do this is to use the JAVA Collections methods to add one tree to another.
Depends on the collection classes that you are using at present.
;JOOP!
0
 
LVL 92

Expert Comment

by:objects
ID: 12284268
> You can't do that.

right you are.
looks like you need to do one at a time as you currently are.
0
 
LVL 21

Accepted Solution

by:
MogalManic earned 125 total points
ID: 12285472
No, I cannot give you code examples, because I haven't written anything like this.  I just know if you Traverse one tree and insert int Tree 2 the Tree will become unbalanced.  For example:
Tree 2 Inserted Into Tree 1:
     2      
  /    \
1      10

     4
  /    \
3       6
will Become
          2      
       /    \
     1      10
           /    \
         3
          \
            4
             \
               6
If you notoce, since the resulting tree retains the same structure, the inserted tree will just be tacked on the end of one of the lists and the tree becomes unbalanced.  The tree will start to degrade into a Linked List.  What you want to have happen is something like this:
   1) The Median of tree 1 is 2
   2) The Median of tree 2 is 4
       (assuming both trees are balanced)
   3) The MIN/MAX of tree 1 is 1,10
   4) The MIN/MAX of tree 2 is 3,6
          4.5-The Min/Max of both trees is 1 and 10
   5) Choose a new root as 4 because 4 is closest to the middle of 10 and 1
       (You could get more complex here and find the closed number between (MIN-MAX)/2=(10-1)/2=9/2=4 but you cannot do this for non-numeric keys)
   6) Iterate through BOTH trees using a PREFIX iterator (in other words visit the nodes 1st then visit the children)
            Create a new tree with 4 as the root
            Insert 2
            Insert 3
            Insert 1
            Insert 10
            Insert 6
The resulting tree is:
          4      
       /     \
     2       10
   /   \     /  
 1      3  6

Another implementation of a tree is called a red-black tree (used by java.util.TreeMap) which automatically rebalances the tree after EVERY insert.  This guarantees that the tree is always balanced which is most efficient for searching.
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

This was posted to the Netbeans forum a Feb, 2010 and I also sent it to Verisign. Who didn't help much in my struggles to get my application signed. ------------------------- Start The idea here is to target your cell phones with the correct…
Introduction This article is the first of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article explains our test automation goals. Then rationale is given for the tools we use to a…
Viewers learn about the third conditional statement “else if” and use it in an example program. Then additional information about conditional statements is provided, covering the topic thoroughly. Viewers learn about the third conditional statement …
Viewers will learn about the different types of variables in Java and how to declare them. Decide the type of variable desired: Put the keyword corresponding to the type of variable in front of the variable name: Use the equal sign to assign a v…
Suggested Courses

636 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question