google-code-prettify

Monday, 17 December 2012

Are two Binary Trees mirror image of each other?

How can you check if two binary trees are mirror image of each other? It would mean that if you do an inorder traversal on the trees, the elements of the second tree will be visited in reversed order compared to the order of the elements visited in the first tree. Here is the Java code:
boolean areMirrorTrees(BinaryTree a, BinaryTree b) {
    if (a == null && b == null) {
        return true;
    }
    if (a == null || b == null) {
        return false;
    }
    return a.data == b.data && areMirrorTrees(a.left, b.right)
            && areMirrorTrees(a.right, b.left);
}
Inorder traversal of the first tree will be: 3, 4, 5, 6, 7, 8, 9, 10, 12, 13.
Inorder traversal of the second tree will be: 13, 12, 10, 9, 8, 7, 6, 5, 4, 3.

1 comment:

  1. video explanation Mirror of Tree's both method and code is discussed : www.youtube.com/watch?v=P40mZ4lWh-A

    ReplyDelete