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

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

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