Check Level Anagrams in Binary Trees

Introduction

Given two binary trees, we need to check whether the nodes at every corresponding level are anagrams of each other.

Two levels are considered anagrams when they contain the same values with the same frequencies, but the order of the values does not matter.

For example:

Tree 1 Level: [3, 2]
Tree 2 Level: [2, 3]

These two levels are anagrams because both contain:

2 → 1 time
3 → 1 time

Therefore, the levels are considered equal.

Example

Consider the following two trees:

Now compare the levels.

Level 0

Tree 1 → [1]
Tree 2 → [1]

Both contain 1.

So:

Level 0 → Anagram

Level 1

Tree 1 → [3, 2]
Tree 2 → [2, 3]

The order is different, but the values and frequencies are the same.

Level 1 → Anagram

Level 2

Tree 1 → [5, 4]
Tree 2 → [4, 5]

Again, both contain the same values.

Level 2 → Anagram

Therefore, the result is:

true

Main Concept

The important concept used in this problem is Level Order Traversal, also called Breadth-First Search (BFS).

A queue is used to process the tree level by level.

For each level:

Find the number of nodes in that level.
Remove those nodes from the queue.
Store their values and frequencies in a HashMap.
Add their children to the queue.
Do the same for the second tree.
Compare the two frequency maps.

If any level has different values or frequencies, the answer is immediately false.

Why HashMap?

We cannot simply compare the values in the order they appear.

For example:

[3, 2]
[2, 3]

The arrays are different if compared directly:

3 != 2

But they are anagrams.

So we need to compare frequencies instead.

We can store:

Tree 1:
3 → 1
2 → 1

and:

Tree 2:
2 → 1
3 → 1

The two maps are equal.

This also handles duplicate values.

For example:

Tree 1 → [2, 3, 2]
Tree 2 → [3, 2, 2]

Frequency map:

2 → 2
3 → 1

for both trees.

Therefore, they are anagrams.

Java Code

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 LinkedList<>();
        Queue<Node> q2 = new LinkedList<>();

        q1.add(root1);
        q2.add(root2);

        while (!q1.isEmpty() && !q2.isEmpty()) {

            int size1 = q1.size();
            int size2 = q2.size();

            // Both levels must contain the same number of nodes
            if (size1 != size2)
                return false;

            HashMap<Integer, Integer> map1 = new HashMap<>();
            HashMap<Integer, Integer> map2 = new HashMap<>();

            for (int i = 0; i < size1; i++) {

                Node node1 = q1.poll();
                Node node2 = q2.poll();

                // Store frequency of values in Tree 1
                map1.put(
                    node1.data,
                    map1.getOrDefault(node1.data, 0) + 1
                );

                // Store frequency of values in Tree 2
                map2.put(
                    node2.data,
                    map2.getOrDefault(node2.data, 0) + 1
                );

                // Add children of Tree 1
                if (node1.left != null)
                    q1.add(node1.left);

                if (node1.right != null)
                    q1.add(node1.right);

                // Add children of Tree 2
                if (node2.left != null)
                    q2.add(node2.left);

                if (node2.right != null)
                    q2.add(node2.right);
            }

            // Compare current level
            if (!map1.equals(map2))
                return false;
        }

        // Both trees must have the same number of levels
        return q1.isEmpty() && q2.isEmpty();
    }
}

Code Explanation

1. Check for null roots

if (root1 == null && root2 == null)
    return true;

if (root1 == null || root2 == null)
    return false;

If both trees are empty, they are considered equal.

If only one tree is empty, they cannot have matching levels.

2. Create two queues

Queue<Node> q1 = new LinkedList<>();
Queue<Node> q2 = new LinkedList<>();

We use one queue for each tree.

Initially, add the root nodes:

q1.add(root1);
q2.add(root2);

The queues allow us to process the trees level by level.

3. Process one level at a time

while (!q1.isEmpty() && !q2.isEmpty()) {

As long as both trees have nodes remaining, we process their current levels.

4. Get the level size

int size1 = q1.size();
int size2 = q2.size();

The queue contains all nodes belonging to the current level.

For example:

        1
       / \
      2   3

Initially:

q = [1]

So:

size = 1

After processing 1, we add 2 and 3:

q = [2, 3]

Now:

size = 2

Therefore, size tells us how many nodes belong to the current level.

5. Compare the number of nodes

if (size1 != size2)
    return false;

If the corresponding levels contain different numbers of nodes, they cannot be anagrams.

For example:

Tree 1 → [2, 3]
Tree 2 → [2, 3, 4]

They have different frequencies and different number of nodes.

So we return:

false

6. Create frequency maps

HashMap<Integer, Integer> map1 = new HashMap<>();
HashMap<Integer, Integer> map2 = new HashMap<>();

These maps store:

Node value → Frequency

For example:

Level = [2, 3, 2, 4]

Map:
2 → 2
3 → 1
4 → 1

7. Process all nodes in the current level

for (int i = 0; i < size1; i++) {

We process exactly size1 nodes because those nodes belong to the current level.

Remove a node:

Node node1 = q1.poll();
Node node2 = q2.poll();

8. Update the frequency

map1.put(
    node1.data,
    map1.getOrDefault(node1.data, 0) + 1
);

Suppose the current level is:

[2, 3, 2]

When 2 is encountered for the first time:

map.getOrDefault(2, 0)

returns 0.

So:

0 + 1 = 1

The map becomes:

2 → 1

When another 2 is found:

1 + 1 = 2

Now:

2 → 2

The same process is performed for the second tree.

9. Add child nodes

After processing the current node, add its children to the queue.

if (node1.left != null)
    q1.add(node1.left);

if (node1.right != null)
    q1.add(node1.right);

Similarly for the second tree:

if (node2.left != null)
    q2.add(node2.left);

if (node2.right != null)
    q2.add(node2.right);

These children will be processed in the next iteration.

10. Compare the frequency maps

After processing the complete level:

if (!map1.equals(map2))
    return false;

For example:

Tree 1:
[3, 2, 3]

Map 1:
3 → 2
2 → 1

Tree 2:

[2, 3, 3]

Map 2:
2 → 1
3 → 2

The maps are equal, so the level is an anagram.

11. Final check

After the loop:

return q1.isEmpty() && q2.isEmpty();

This ensures that both trees have finished at the same time.

If one tree still has nodes while the other does not, their structures have different levels, so the answer should be false.

Dry Run

Consider:

First iteration

q1 = [1]
q2 = [1]

Maps:

map1 = {1=1}
map2 = {1=1}

Equal → Continue.

Queues become:

q1 = [3, 2]
q2 = [2, 3]

Second iteration

q1 = [3, 2]
q2 = [2, 3]

Maps:

map1 = {3=1, 2=1}
map2 = {2=1, 3=1}

The maps are equal.

Continue.

Third iteration

q1 = [5, 4]
q2 = [4, 5]

Maps:

map1 = {5=1, 4=1}
map2 = {4=1, 5=1}

Again equal.

Both queues are now empty.

Result:

true

Example Where the Answer Is False

Consider:

Level 0:

[1] vs [1]

Anagram.

Level 1:

[2, 3] vs [2, 4]

Frequency maps:

Tree 1:
2 → 1
3 → 1

Tree 2:
2 → 1
4 → 1

The maps are different.

Therefore:

false

The algorithm immediately returns false without processing the remaining levels.

Complexity Analysis

Let n be the total number of nodes.

Time Complexity

Each node is inserted into and removed from a queue once.

Each node also contributes once to a frequency map.

Therefore:

Time Complexity = O(n)

Auxiliary Space

The queues can contain nodes from a level, and the frequency maps can contain values from a level.

In the worst case, a level can contain O(n) nodes.

Therefore:

Auxiliary Space = O(n)

Important Interview Point

The key idea to remember is:

Use BFS to compare corresponding levels and use HashMap to compare the frequency of node values without considering their order.

The combination is:

Binary Tree
     ↓
Level Order Traversal (BFS)
     ↓
Get nodes at each level
     ↓
Store value frequencies using HashMap
     ↓
Compare both maps
     ↓
If every level matches → true
Otherwise → false

This approach satisfies the required:

Time  : O(n)
Space : O(n)

and is suitable for a binary tree containing up to 10^5 nodes.