Tutorial :Binary Trees question. Checking for similar shape



Question:

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?


Solution:1

You can easily do that 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 check two trees, pass their root nodes to the function above.

equalTrees(tree1.root(), tree2.root())  


Solution:2

Two Breadth First Searches in parallel would be one way.

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

With BFS, you can examine all nodes a particular level of the tree at the same time. That way, if you don't distinguish between right and left children (i.e. if your tree is considered the same if a node's counterpart has one child, regardless of "right" or "left" child) you can handle that at that time.


Solution:3

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

You will be pleased to know that binary trees have an interesting property: they can be represented as arrays. Simply convert each tree to one of these arrays and compare the array contents. Blank cells correspond to left or right children that don't exist, defining the structure of the tree. You want to iterate over both arrays and make sure that each blank cell encountered in one array appears in the other array; this is O(n).

Of course, if the arrays are different sizes, you don't have to do any work at all, since trees with different numbers of nodes can't possibly have identical structure. From there, you're all done.


Solution:4

Walk them in pre-order and in-order with symbolic names instead of the actual data and compare the resulting Strings. Maybe some more input on your data structure would be usefull.

Not java related AFAICT


Solution:5

Just follow the branches, mimicking each move in one tree in the other. 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)  

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »