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?

Answer 1

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.

Answer 2

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

Answer 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.

Answer 4

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)

Answer 5

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())