291. Check if All Levels of Two Binary Trees Are Anagrams

Two binary trees are given, each described level by level (as you'd get from a queue-based level-order traversal): first the number of levels, then for each level a count followed by that many node values (children of null nodes are simply omitted, so a level's list is just the values of the nodes that actually exist at that depth). The trees are 'level-anagram equal' if they have the same number of levels and, for every depth, the multiset of node values at that depth in one tree is a permutation (anagram) of the multiset at that depth in the other tree - position within the level doesn't matter. Print 'Yes' if the two trees are level-anagram equal, otherwise 'No'.

Input: For each of the two trees in turn: a line with the number of levels, then for each level a line starting with that level's node count followed by that many space-separated node values. Output: Print 'Yes' if the two trees have the same number of levels and every level's multiset of values matches between them, otherwise print 'No'.

1 <= number of levels of either tree <= 1000, 0 <= nodes per level <= 10^5, node values fit in a 32-bit signed integer

This problem hands you the levels pre-extracted, but in a REAL tree (not given level-by-level already), a queue-based BFS is exactly how you'd naturally produce these same per-level lists in the first place - which is exactly why this problem lives in the Queue category.

Given two trees described level by level, check whether both trees have the same number of levels AND, for every single level, the exact same collection of values (regardless of left-to-right order within that level). Brute force: For each level, sort both lists and compare them directly for exact equality after sorting - this correctly checks the anagram condition (since sorted equal lists means same multiset), though it costs a sort per level rather than a simpler counting pass. Optimised: Since this problem is fundamentally about comparing MULTISETS (not sequences), a frequency-count comparison per level (counting how many times each value appears in each of the two lists and comparing those counts) avoids the sorting cost entirely, checking anagram-equality in linear time per level instead of n log n per level.

First check the two trees have the same number of levels; if not, immediately print 'No'. Otherwise, for each corresponding depth, take the two lists of node values, sort both, and compare them element by element for exact equality - two sorted multisets are anagrams of each other exactly when the sorted sequences match. This is correct because sorting normalizes away any ordering differences, but sorting every level costs an extra logarithmic factor on top of the total number of nodes. Time: O(N log N) Space: O(N)

Use one hashmap per level instead of two: increment counts for every value seen in tree A's level and decrement for every value seen in tree B's level in a single combined pass, then check that all counts are zero. Also check the level count and level sizes level-by-level as you go, and stop immediately and print 'No' the moment any level fails to match rather than processing all remaining levels regardless. This keeps the same overall linear time bound as the hashmap approach in the worst case but roughly halves the hashmap operations per level and, on inputs that differ early, finishes far faster in practice since it never bothers examining levels after the first mismatch. Time: O(N) Space: O(max level size)

For each level, build a frequency hashmap of the values in tree A's level, then walk through tree B's level decrementing the corresponding counts (or marking a mismatch immediately if a value from B isn't present with a remaining positive count). If every count nets to zero, the level's multisets match. This checks anagram equality in time proportional to the level size without needing to sort, which removes the log factor that sorting incurs and is a genuine algorithmic improvement over the brute-force approach. Time: O(N) Space: O(max level size)

1. Since the input is already given level by level (exactly what you'd get from a queue-based breadth-first traversal of each tree), read each tree's per-level lists directly. 2. First check both trees have the SAME NUMBER of levels - if not, the answer is immediately No. 3. For each corresponding pair of levels, check whether they contain the same VALUES the same number of times each (an anagram check - same multiset), ignoring the order values appear within the level. 4. If every single level passes this multiset check, the trees are level-anagram equal - answer Yes.

Time: Proportional to the total number of nodes across both trees - each level's nodes are processed a small, constant number of times (once to count, once to compare). Space: Proportional to the number of nodes in the largest single level, for the frequency-count structures used per level.

the two trees having a different number of levels, which is an immediate 'No' (per the hints); a level with 0 nodes, so no values follow its count; the same values appearing in a different order within a level, which still counts as 'Yes' since it's a multiset comparison.

Be ready to explain that this problem is really 'anagram check, applied level by level' - explicitly connecting it to the more familiar single-string anagram-checking problem is a strong way to demonstrate you're recognizing patterns, not solving from scratch.