[Last Call] Learn about multicloud storage options and how to improve your company's cloud strategy. Register Now

x
?
Solved

Binary Trees question.  Checking for similar shape

Posted on 2009-04-12
6
Medium Priority
?
263 Views
Last Modified: 2013-11-23
Hi I'm stuck doing this, not sure how to go about it.

If I have two binary trees, how would I check if the have the same shape? Data in the nodes doesn't matter, just if the tree structures are equal.

Any ideas on how to solve this problem?
0
Comment
Question by:ubuntuguy
[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
6 Comments
 
LVL 25

Accepted Solution

by:
InteractiveMind earned 840 total points
ID: 24126028
How exactly do you define 'same shape'? Suppose two trees are the reflection of each other (so they're symmetric), would you consider them the same?

You could just start with the first node on each tree; count the number of sub-nodes. If they're the same, then for each sub-node, count their sub-nodes, are they the same in each case? And so on.
0
 
LVL 1

Author Comment

by:ubuntuguy
ID: 24126073
well i meant the structures are the same. data in the nodes can be different. i.e.

                      3
                   /       \
                4        23
              /              
          34  

and
                      5
                    /       \
                 9         99
               /              
           44

have the same structure.  on the other hand

                      3
                    /       \
                 4        23
               /              
           34  


and

                      3
                    /       \
                 4        23
               /  \            
           34   55

dont have the same structure.  
               
0
 
LVL 6

Expert Comment

by:crossdev
ID: 24126089
If you want a binary tree, meaning that it could be unbalanced you'll need to create one.  Otherwise there is an implmenetation of a Red / Black tree which will stay balanced called TreeMap

http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeMap.html
0
Independent Software Vendors: 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!

 
LVL 6

Expert Comment

by:crossdev
ID: 24126096
Ignore that last post.

You could create an algorithm that counted the number of leaf nodes and then checked the length of each leaf.  

So the top exampl has 2 leafs with a depth os 3 & 2 :  [3,2]

The fourth one has three leafs with depths of [3,3,2]

You could use this signature to determine.
0
 
LVL 6

Assisted Solution

by:crossdev
crossdev earned 60 total points
ID: 24126106
Keep in mind this sort of exercise is to test your ability to trouble shoot.  The solution itself has little usefulness.  however your ability to solve it is what matters.  If you find such a problem difficult or impossible, consider another career path.  

I should not that the solution I gave will get you on the right track but is not the entire solution.  I don;t like solving peoples homework.  Iwill nudge you in the right direction.  If anyone gives you the solution, I hope they employ you caue I'll weed you out.  Short cuts only affect you.  If you take the time to figure it out you'll be doing yourself no harm, but if you try to short cut the process you will only hurt your learning process.

Good luck.
0
 
LVL 84

Assisted Solution

by:ozo
ozo earned 600 total points
ID: 24126898
same( a,b){
  if( a is a terminal node and b is a terminal node ) return true
  if( a is an interior node and b is an interior node and same(a.left,b.left) and same(a.right,b.right) ) return true
  else return false;
}
0

Featured Post

Industry Leaders: 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

One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
Video by: Michael
Viewers learn about how to reduce the potential repetitiveness of coding in main by developing methods to perform specific tasks for their program. Additionally, objects are introduced for the purpose of learning how to call methods in Java. Define …
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
Suggested Courses

650 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