Geek Answers Handbook

Question about binary trees. Verification of a similar form

Hi, I'm stuck on this, not sure how to do this.

If I have two binary trees, how would I check if they have the same shape? The data in the nodes does not matter only if the tree structures are equal.

Any ideas on how to solve this problem?

+4
source share
5 answers

You can easily do this with recursion. This following code works because two non-empty trees have the same shape if and only if their respective subtrees have the same shape.

boolean equalTrees(Node lhs, Node rhs) { // Empty trees are equal if (lhs == null && rhs == null) return true; // Empty tree is not equal to a non-empty one if ((lhs == null && rhs != null) || (lhs != null && rhs == null)) return false; // otherwise check recursively return equalTrees(lhs.left(), rhs.left()) && equalTrees(lhs.right(), rhs.right()) }

To test two trees, translate their root nodes into the above function.

 equalTrees(tree1.root(), tree2.root())
+14
source

Two parallel parallel parallel scans will be one way.

http://en.wikipedia.org/wiki/Breadth-first_search

Using BFS, you can simultaneously check all the nodes of a certain tree level. Thus, if you do not distinguish between right and left children (i.e. if your tree is considered the same, if a peer node has one child, regardless of the "right" or "left" child), you can handle this time.

+2
source

If I have two binary trees, how would I check if they have the same shape?

You will be pleased to know that binary trees have an interesting property: they can be represented as arrays . Just convert each tree to one of these arrays and compare the contents of the array. Empty cells correspond to left or right child elements that do not exist, defining the structure of the tree. You want to iterate over both arrays and make sure that every empty cell that appears in one array appears in another array; this is O (n).

Of course, if the arrays are of different sizes, you do not need to do any work at all, since trees with different numbers of nodes cannot have the same structure. From there you are all done.

+2
source

Post them in preliminary order and in order with symbolic names instead of actual data and compare the resulting lines. Additional input in your data structure might be helpful.

Non-Java AFAICT

0
source

Just follow the branches, simulating each movement in one tree in another. In Python pseudo code:

  class Tree:
     def __init __ (self, value, left = None, right = None):
         self.value = value
         self.left = left
         self.right = right

 def same_shape (T1, T2):
     if T1 == None:
         return T2 == None

     if T2 == None:
         return T1 == None

     return same_shape (T1.left, T2.left) and same_shape (T1.right, T2.right)
0
source

More articles:


All Articles