Tree Isomorphism Problem

The problem, simply

You get two binary trees. A flip at a node swaps its left and right child (each child keeps its own family). The two trees are isomorphic if you can make the first one look exactly like the second by flipping any nodes you like, any number of times. Values never change.

Return true or false.

A story to remember it

Picture it

Examples

Way 1: the simple way

Compare the two roots. If the values match, try both ways for the children: straight (left with left, right with right) or flipped (left with right, right with left). If either way works all the way down, the trees match.

1. Both empty: true. Only one empty: false.
2. Values differ: false.
3. Return (same(a.left, b.left) and same(a.right, b.right)) or (same(a.left, b.right) and same(a.right, b.left)).

class Solution {
    public boolean isIsomorphic(TreeNode a, TreeNode b) {
        if (a == null && b == null) return true;
        if (a == null || b == null) return false;
        if (a.val != b.val) return false;
        return (isIsomorphic(a.left, b.left) && isIsomorphic(a.right, b.right))   // straight
            || (isIsomorphic(a.left, b.right) && isIsomorphic(a.right, b.left));  // flipped
    }
}

How long it takes: when all values are different, the wrong pairing fails right at the first values, so it is about O(n). With repeated values, both pairings can go deep. Each pair of nodes (one from each tree) is compared at most once, so the worst case is O(n * m). Extra room: the call stack, O(h).

Way 2: the clever way

Give every subtree a name that ignores flips. Then two trees match exactly when their roots get the same name.

1. An empty spot is named 0.
2. For a node, first name its two children, say x and y.
3. Its shape is the triple (value, smaller of x and y, bigger of x and y). Putting the smaller name first is what makes a flip invisible.
4. Look the shape up in a shared shape book (a hash map). If it is new, give it the next free number. That number is the node's name.
5. Name both trees with the same book and compare the two root names.

import java.util.*;

class Solution {
    private Map<String, Integer> book = new HashMap<>();   // shape -> name

    public boolean isIsomorphic(TreeNode a, TreeNode b) {
        book.clear();
        return name(a) == name(b);          // same book for both trees
    }

    private int name(TreeNode node) {
        if (node == null) return 0;         // an empty spot is named 0
        int x = name(node.left), y = name(node.right);
        String shape = node.val + "," + Math.min(x, y) + "," + Math.max(x, y);  // order does not matter
        Integer id = book.get(shape);
        if (id == null) {
            id = book.size() + 1;           // a new shape gets the next number
            book.put(shape, id);
        }
        return id;
    }
}

How long it takes: each node is named once, with one map lookup, about O(n + m). Extra room: the shape book, O(n + m).

Watch out for

• Check a == null && b == null before a == null || b == null, or two empty trees return false.
• In Way 1, use || between the two pairings and && inside each. Mixing them up accepts trees where the left fits one way and the right fits the other way.
• In Way 2, both trees must use the same shape book. Two separate books hand out numbers in a different order.

What interviewers ask next

• Flip equivalent trees (LeetCode 951) is this exact problem.
• Are two trees mirror images? Only the flipped pairing is allowed at every node.
• Group many trees into "same up to flips" families. Name them all with one shared book; trees with the same root name are in the same family. Way 1 would compare every pair.
• Unlabelled trees, or trees where nodes have any number of children. Sort the children's names instead of taking min and max. This is the classic AHU idea for checking if two rooted trees have the same shape.

Remember this

Grown-up words: spinning a bar is flipping the children, the short name is a canonical form, the shape book is a hash map used for hashing subtrees, and the two kinds of check are a depth first search with two branches.