Check if all levels of two trees are anagrams
Problem
Given two binary trees, return true if, for every level, the multiset of values on that level is the same in both trees.
Example 1
Input: tree1 = [1, 3, 2, 5, 4], tree2 = [1, 2, 3, 4, 5] Output: true
Also asked as: Check if all levels of two trees are anagrams or not
Test cases
Case 1
Input: [1,3,2,5,4], [1,2,3,4,5] Expected: true
Case 2
Input: [1,2,3], [1,2,4] Expected: false
Case 3
Input: [1,2], [1,2,3] Expected: false
Case 4
Input: [1], [1] Expected: true
View solutionHide solution1 approach
1. Level-order both trees, compare sorted level values
Time O(n log n)Space O(width)
BFS each tree level by level; two levels are anagrams iff their multisets of values match.
function levelsAreAnagrams(a, b) { let qa = a ? [a] : [], qb = b ? [b] : []; while (qa.length && qb.length) { if (qa.length !== qb.length) return false; const va = qa.map((n) => n.val).sort((x, y) => x - y); const vb = qb.map((n) => n.val).sort((x, y) => x - y); if (va.join(',') !== vb.join(',')) return false; const na = [], nb = []; for (const n of qa) { if (n.left) na.push(n.left); if (n.right) na.push(n.right); } for (const n of qb) { if (n.left) nb.push(n.left); if (n.right) nb.push(n.right); } qa = na; qb = nb; } return qa.length === 0 && qb.length === 0;}