Check Level Anagrams in Binary Trees

Problem Overview

Two trees are level-anagrams when every corresponding level holds the same multiset of values.

Intuition

Two trees are level-anagrams when every corresponding level holds the same multiset of values. Breadth-first search visits levels in order; comparing frequency maps per level is enough and avoids sorting.

Algorithm

1Return true if both roots are null, false if exactly one is null.
2BFS both trees with queues of equal starting size.
3For each level, if queue sizes differ, return false.
4Poll paired nodes: add +1 for tree1 values and -1 for tree2 values in one map.
5Enqueue children from both nodes.
6If any frequency is nonzero after the level, return false.
7After the first queue empties, return whether the second queue is also empty.

Example Walkthrough

Input: same values per level, possibly different child order

1. Level 0 values match.
2. Level 1 multisets match after counting.
3. All later levels agree, so the answer is true.

Output: true

Common Pitfalls

• Structure can differ; only the multiset per level matters.
• Unequal level widths mean the trees are not level-anagrams.
• Sorting each level works but is slower than counting.
• Empty trees are anagrams of each other; one empty and one nonempty is not.

Check Level Anagrams in Binary Trees.java

Java

// Approach: Level-order both trees in lockstep. A level is an anagram iff the
// multisets of node values match. Count frequencies from one tree and subtract
// with the other instead of sorting each level.
// Complexity: O(n) time, O(w) space (w = max width).
import java.util.*;

class Solution {
    public boolean areAnagrams(Node root1, Node root2) {
        if (root1 == null && root2 == null)
            return true;
        if (root1 == null || root2 == null)
            return false;

        Queue<Node> q1 = new ArrayDeque<>();
        Queue<Node> q2 = new ArrayDeque<>();
        q1.offer(root1);
        q2.offer(root2);

        while (!q1.isEmpty()) {
            if (q1.size() != q2.size())
                return false;

            int size = q1.size();
            Map<Integer, Integer> freq = new HashMap<>();

            for (int i = 0; i < size; i++) {
                Node a = q1.poll();
                Node b = q2.poll();
                freq.merge(a.data, 1, Integer::sum);
                freq.merge(b.data, -1, Integer::sum);

                if (a.left != null)
                    q1.offer(a.left);
                if (a.right != null)
                    q1.offer(a.right);
                if (b.left != null)
                    q2.offer(b.left);
                if (b.right != null)
                    q2.offer(b.right);
            }

            for (int c : freq.values()) {
                if (c != 0)
                    return false;
            }
        }

        return q2.isEmpty();
    }
}

class Node {
    int data;
    Node left, right;

    Node(int x) {
        data = x;
    }
}

Was this solution helpful?