Check if all levels of two trees are anagrams or not

The problem, simply

You get two binary trees. Look at them row by row, from the top. Row 0 of the first tree must hold the same values as row 0 of the second tree, with the same counts, but the order inside the row does not matter. The same goes for row 1, row 2, and so on.

Return true if every row passes, and false otherwise. The two trees must also have the same number of rows.

A story to remember it

Picture it

Examples

Way 1: the simple way

Read both trees row by row, write each row down as a list, sort both lists, and compare them.

1. Run a level order walk on both trees at the same time.
2. If the two rows have different sizes, return false.
3. Sort both rows. If they are not equal, return false.
4. If one tree runs out of rows before the other, return false.

class Solution {
    public boolean levelsAreAnagrams(TreeNode a, TreeNode b) {
        Queue<TreeNode> q1 = new ArrayDeque<>(), q2 = new ArrayDeque<>();
        if (a != null) q1.add(a);
        if (b != null) q2.add(b);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            List<Integer> row1 = readRow(q1), row2 = readRow(q2);
            if (row1.size() != row2.size()) return false;
            Collections.sort(row1);
            Collections.sort(row2);
            if (!row1.equals(row2)) return false;
        }
        return q1.isEmpty() && q2.isEmpty();     // same number of rows
    }

    private List<Integer> readRow(Queue<TreeNode> q) {
        List<Integer> row = new ArrayList<>();
        for (int i = q.size(); i > 0; i--) {
            TreeNode node = q.poll();
            row.add(node.val);
            if (node.left != null) q.add(node.left);
            if (node.right != null) q.add(node.right);
        }
        return row;
    }
}

How long it takes: each node is read once, but sorting the rows costs up to O(n log n) in total. Extra room: the queues and one row at a time, all bounded by the widest row w, so O(w).

Way 2: the clever way

Skip the sorting. Count instead, like the tally marks.

1. Keep a waiting line, a queue, for each tree. Put each root in its line.
2. While both lines are non-empty, read their sizes. If the sizes differ, return false.
3. Take that many nodes from line 1. For each value, add one tally in a hash map. Put its children at the back of line 1.
4. Take that many nodes from line 2. For each value, rub out one tally. If there is no tally to rub out, return false. Put its children at the back of line 2.
5. Both rows had the same size and no rub out failed, so every tally is gone. Move to the next row.
6. At the end, both lines must be empty together.

class Solution {
    public boolean levelsAreAnagrams(TreeNode a, TreeNode b) {
        Queue<TreeNode> q1 = new ArrayDeque<>(), q2 = new ArrayDeque<>();
        if (a != null) q1.add(a);
        if (b != null) q2.add(b);
        while (!q1.isEmpty() && !q2.isEmpty()) {
            int size = q1.size();
            if (size != q2.size()) return false;          // rows of different length
            Map<Integer, Integer> tally = new HashMap<>();
            for (int i = 0; i < size; i++) {               // tree 1 adds tallies
                TreeNode node = q1.poll();
                tally.merge(node.val, 1, Integer::sum);
                if (node.left != null) q1.add(node.left);
                if (node.right != null) q1.add(node.right);
            }
            for (int i = 0; i < size; i++) {               // tree 2 rubs them out
                TreeNode node = q2.poll();
                Integer have = tally.get(node.val);
                if (have == null) return false;            // no tally to rub out
                if (have == 1) tally.remove(node.val);
                else tally.put(node.val, have - 1);
                if (node.left != null) q2.add(node.left);
                if (node.right != null) q2.add(node.right);
            }
        }
        return q1.isEmpty() && q2.isEmpty();               // same number of rows
    }
}

How long it takes: every node is added to its line once, taken out once, and touches the map once, O(n). Extra room: each line and the map hold at most one row, the widest row w, so O(w).

Watch out for

• Compare row sizes first. Without it, a short row in tree 2 might rub out only part of the tallies and look fine.
• Use counts, not a set. [5, 7] and [7, 7] have the same set of values but are not anagrams.
• Save the row size before the loop. Children join the line during the loop, so q.size() keeps changing.
• One empty tree and one non-empty tree must give false. The final check handles it.

What interviewers ask next

• Can you do it with depth first search? Yes. Walk each tree with a depth counter and add val to a list for that depth. Then compare the lists per depth with counting. Same O(n) time, but it stores every row at once.
• Check if two trees are mirror images instead. Then order matters: compare left of one with right of the other, recursively.
• Check if each row is a palindrome. Read the row into a list and compare from both ends.
• The values are small, say 0 to 9. Use an int[10] count array instead of a hash map; it is faster and simpler.
• How do you find the widest row w? It is the largest size seen in this same loop.

Remember this

Grown-up words: the photo steps are levels, reading them in order is level order traversal or breadth first search, the waiting lines are queues, the tally sheet is a hash map of counts, and "same values with the same counts" is an anagram (a multiset match).