Check if all levels of two trees are anagrams

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}