Stacks & QueuesProblem 34 of 38
Check if all levels of two trees are anagrams or not
Problem Statement
Given two binary trees, check if all the levels of the two trees are anagrams of each other. Two levels are anagrams if they contain the same elements with the same frequency, regardless of order.
Example:
Tree 1: Tree 2:
1 1
/ \ / \
2 3 3 2
/ \ \ / / \
4 5 6 6 5 4
Level 0: [1] vs [1] ✓ (Anagram)
Level 1: [2,3] vs [3,2] ✓ (Anagram)
Level 2: [4,5,6] vs [6,5,4] ✓ (Anagram)
Output: true (All levels are anagrams)
Approach 1: Brute Force (Sort and Compare)
Intuition
Perform level order traversal on both trees simultaneously. For each level, collect all node values, sort them, and compare. If all levels match, the trees have anagram levels.
Algorithm
- Perform BFS on both trees level by level
- For each level, collect values in vectors
- Sort both vectors and compare
- If any level doesn't match, return false
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class AnagramLevels {
public static boolean areAnagramsBruteForce(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
Queue<TreeNode> q1 = new LinkedList<>();
Queue<TreeNode> q2 = new LinkedList<>();
q1.offer(root1);
q2.offer(root2);
while (!q1.isEmpty() && !q2.isEmpty()) {
int size1 = q1.size();
int size2 = q2.size();
if (size1 != size2) return false;
List<Integer> level1 = new ArrayList<>();
List<Integer> level2 = new ArrayList<>();
for (int i = 0; i < size1; i++) {
TreeNode node = q1.poll();
level1.add(node.val);
if (node.left != null) q1.offer(node.left);
if (node.right != null) q1.offer(node.right);
}
for (int i = 0; i < size2; i++) {
TreeNode node = q2.poll();
level2.add(node.val);
if (node.left != null) q2.offer(node.left);
if (node.right != null) q2.offer(node.right);
}
Collections.sort(level1);
Collections.sort(level2);
if (!level1.equals(level2)) return false;
}
return q1.isEmpty() && q2.isEmpty();
}
}Complexity Analysis
- Time Complexity: O(n * m * log(m)) - n levels, m nodes per level, sorting takes O(m log m)
- Space Complexity: O(m) - storing level values
Approach 2: Optimal (Using HashMap/Counter)
Intuition
Instead of sorting, use a hash map to count frequency of values at each level. Add values from tree1, subtract values from tree2. If all counts are zero, it's an anagram.
Algorithm
- Perform BFS on both trees level by level
- For each level, build frequency map from tree1
- Decrement frequencies using values from tree2
- If any non-zero frequency remains, not an anagram
java
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class AnagramLevels {
public static boolean areAnagrams(TreeNode root1, TreeNode root2) {
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
Queue<TreeNode> q1 = new LinkedList<>();
Queue<TreeNode> q2 = new LinkedList<>();
q1.offer(root1);
q2.offer(root2);
while (!q1.isEmpty() && !q2.isEmpty()) {
int size1 = q1.size();
int size2 = q2.size();
if (size1 != size2) return false;
Map<Integer, Integer> freq = new HashMap<>();
// Add frequencies from tree 1
for (int i = 0; i < size1; i++) {
TreeNode node = q1.poll();
freq.put(node.val, freq.getOrDefault(node.val, 0) + 1);
if (node.left != null) q1.offer(node.left);
if (node.right != null) q1.offer(node.right);
}
// Subtract frequencies from tree 2
for (int i = 0; i < size2; i++) {
TreeNode node = q2.poll();
freq.put(node.val, freq.getOrDefault(node.val, 0) - 1);
if (freq.get(node.val) < 0) return false;
if (node.left != null) q2.offer(node.left);
if (node.right != null) q2.offer(node.right);
}
// Check all frequencies are zero
for (int count : freq.values()) {
if (count != 0) return false;
}
}
return q1.isEmpty() && q2.isEmpty();
}
public static void main(String[] args) {
TreeNode root1 = new TreeNode(1);
root1.left = new TreeNode(2);
root1.right = new TreeNode(3);
root1.left.left = new TreeNode(4);
root1.left.right = new TreeNode(5);
root1.right.right = new TreeNode(6);
TreeNode root2 = new TreeNode(1);
root2.left = new TreeNode(3);
root2.right = new TreeNode(2);
root2.left.left = new TreeNode(6);
root2.right.left = new TreeNode(5);
root2.right.right = new TreeNode(4);
System.out.println("Are anagrams: " + areAnagrams(root1, root2)); // true
}
}Complexity Analysis
- Time Complexity: O(n * m) - n levels, m nodes per level, O(1) hash operations
- Space Complexity: O(m) - hash map for level frequencies
Key Takeaways
- Level Order Traversal: BFS is key for level-by-level comparison
- Anagram Check: Use frequency counting instead of sorting
- Early Termination: Return false as soon as mismatch is found
- Queue-based BFS: Queues enable level-by-level processing
- HashMap Efficiency: O(1) lookup vs O(n log n) sorting
- This combines tree traversal with anagram detection concepts