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:

Code

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

These two levels are anagrams because both contain:

Code

2 → 1 time
3 → 1 time

Therefore, the levels are considered equal.

Example

Consider the following two trees:

Code

Code

Now compare the levels.

Level 0

Code

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

Both contain 1.

So:

Code

Level 0 → Anagram

Level 1

Code

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

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

Code

Level 1 → Anagram

Level 2

Code

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

Again, both contain the same values.

Code

Level 2 → Anagram

Therefore, the result is:

Code

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:

Code

[3, 2]
[2, 3]

The arrays are different if compared directly:

Code

3 != 2

But they are anagrams.

So we need to compare frequencies instead.

We can store:

Code

Tree 1:
3 → 1
2 → 1

and:

Code

Tree 2:
2 → 1
3 → 1

The two maps are equal.

This also handles duplicate values.

For example:

Code

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

Frequency map:

Code

2 → 2
3 → 1

for both trees.

Therefore, they are anagrams.

Java Code

Java

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

Java

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

Java

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

We use one queue for each tree.

Initially, add the root nodes:

Java

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

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

3. Process one level at a time

Java

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

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

4. Get the level size

Java

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

The queue contains all nodes belonging to the current level.

For example:

Code

        1
       / \
      2   3

Initially:

Code

q = [1]

So:

Code

size = 1

After processing 1, we add 2 and 3:

Code

q = [2, 3]

Now:

Code

size = 2

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

5. Compare the number of nodes

Java

if (size1 != size2)
    return false;

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

For example:

Code

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

They have different frequencies and different number of nodes.

So we return:

Code

false

6. Create frequency maps

Java

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

These maps store:

Code

Node value → Frequency

For example:

Code

Level = [2, 3, 2, 4]

Map:
2 → 2
3 → 1
4 → 1

7. Process all nodes in the current level

Java

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

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

Remove a node:

Java

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

8. Update the frequency

Java

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

Suppose the current level is:

Code

[2, 3, 2]

When 2 is encountered for the first time:

Code

map.getOrDefault(2, 0)

returns 0.

So:

Code

0 + 1 = 1

The map becomes:

Code

2 → 1

When another 2 is found:

Code

1 + 1 = 2

Now:

Code

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.

Java

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

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

Similarly for the second tree:

Java

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:

Java

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

For example:

Code

Tree 1:
[3, 2, 3]

Map 1:
3 → 2
2 → 1

Tree 2:

Code

[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:

Java

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:

Code

Code

First iteration

Code

q1 = [1]
q2 = [1]

Maps:

Code

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

Equal → Continue.

Queues become:

Code

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

Second iteration

Code

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

Maps:

Code

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

The maps are equal.

Continue.

Third iteration

Code

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

Maps:

Code

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

Again equal.

Both queues are now empty.

Result:

Code

true

Example Where the Answer Is False

Consider:

Code

Code

Level 0:

Code

[1] vs [1]

Anagram.

Level 1:

Code

[2, 3] vs [2, 4]

Frequency maps:

Code

Tree 1:
2 → 1
3 → 1

Tree 2:
2 → 1
4 → 1

The maps are different.

Therefore:

Code

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:

Code

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:

Code

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:

Code

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:

Code

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

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