**π‘ Problem Formulation:** We need to determine whether all corresponding levels in two binary trees are anagrams of each other. To clarify, two trees are considered to have levels that are anagrams if, for every level, the nodes at that depth can be rearranged to match the other tree’s nodes for the same level. For example, given two trees, one with level 1 nodes [1,2] and the other with level 1 nodes [2,1], they are anagrams. We must verify this for all levels.

## Method 1: Using Level Order Traversal and Sorting

This method involves performing a level order traversal of both trees, collecting nodes at each level as a list, and then sorting these lists. If the sorted lists are identical for all corresponding levels, then the levels are anagrams. Functionally, this can be defined as `areLevelsAnagrams(tree1, tree2)`

, returning `True`

if all levels are anagrams and `False`

otherwise.

Here’s an example:

from collections import deque class TreeNode: def __init__(self, x): self.val = x self.left = None self.right = None def areLevelsAnagrams(tree1, tree2): def levelOrderTraversal(tree): if not tree: return [] levels = [] queue = deque([tree]) while queue: level_length = len(queue) level = [] for _ in range(level_length): node = queue.popleft() if node: level.append(node.val) queue.append(node.left) queue.append(node.right) levels.append(level) return levels levels1, levels2 = levelOrderTraversal(tree1), levelOrderTraversal(tree2) return all(sorted(level1) == sorted(level2) for level1, level2 in zip(levels1, levels2)) # Example Trees tree1 = TreeNode(1) tree1.left = TreeNode(3) tree1.right = TreeNode(2) tree1.right.left = TreeNode(5) tree1.right.right = TreeNode(4) tree2 = TreeNode(1) tree2.left = TreeNode(2) tree2.right = TreeNode(3) tree2.left.left = TreeNode(4) tree2.left.right = TreeNode(5) print(areLevelsAnagrams(tree1, tree2))

The output of this code snippet:

True

This code snippet defines the function `areLevelsAnagrams()`

, which checks if all levels of two binary trees are anagrams. It performs a level order traversal of each tree and uses a double-ended queue to store the nodes level by level. It then compares the sorted representations of each level’s nodes in both trees, returning True if they are all equal.

## Method 2: Using Recursive Preorder Traversal

This algorithm leverages a recursive preorder traversal to collect nodes at each depth, using a dictionary to track the counts of node values at each level for both trees. If the counted values match at each level across both trees, they’re anagrams. It can be encapsulated in a function `areLevelAnagramsRecursive(tree1, tree2)`

.

Here’s an example:

from collections import defaultdict def areLevelAnagramsRecursive(tree1, tree2): def preorderTraversal(node, level, levels_dict): if node: levels_dict[level][node.val] += 1 preorderTraversal(node.left, level + 1, levels_dict) preorderTraversal(node.right, level + 1, levels_dict) levels_dict1, levels_dict2 = defaultdict(lambda: defaultdict(int)), defaultdict(lambda: defaultdict(int)) preorderTraversal(tree1, 0, levels_dict1) preorderTraversal(tree2, 0, levels_dict2) return all(levels_dict1[level] == levels_dict2[level] for level in levels_dict1) # Using the same example trees from Method 1 print(areLevelAnagramsRecursive(tree1, tree2))

The output of this code snippet:

True

This snippet defines `areLevelAnagramsRecursive()`

, which uses a recursive preorder traversal with a helper function to build a dictionary of counts of node values at each level. It checks for the equality of these dictionaries for corresponding levels in both trees to determine if the levels are anagrams or not.

## Method 3: Hash Function-Based Verification

Instead of sorting, this method applies a hash function to each level’s nodes to generate a unique hash value. If the hash values for the levels in both trees match, the trees levels are considered anagrams. Encapsulated in a function as `areLevelsAnagramsUsingHash(tree1, tree2)`

.

Here’s an example:

from collections import deque def areLevelsAnagramsUsingHash(tree1, tree2): def hashFunction(level): return sum(hash(node) for node in level) def levelOrderTraversal(tree): # Previous level order traversal implementation # [...] levels1_hashed = [hashFunction(level) for level in levelOrderTraversal(tree1)] levels2_hashed = [hashFunction(level) for level in levelOrderTraversal(tree2)] return levels1_hashed == levels2_hashed # Using the same example trees from Method 1 print(areLevelsAnagramsUsingHash(tree1, tree2))

The output of this code snippet:

True

This code uses a `hashFunction()`

that creates a summed hash value for a level’s nodes. The `levelOrderTraversal()`

function is used again to generate the levels with their hashed values, and the final comparison is based on these hash results, thereby checking if the levels are anagrams.

## Method 4: Breadth-First Search with Counter

This approach performs a breadth-first search (BFS) on both trees simultaneously, using a `Counter`

to tally the node values at each level. The levels are anagrammatic if the counts are equal across both trees at the same level. This can be functionally represented by `areLevelsAnagramsBFS(tree1, tree2)`

.

Here’s an example:

from collections import deque, Counter def areLevelsAnagramsBFS(tree1, tree2): queue1, queue2 = deque([(tree1, 0)]), deque([(tree2, 0)]) levels1, levels2 = defaultdict(Counter), defaultdict(Counter) while queue1 and queue2: node1, level1 = queue1.popleft() node2, level2 = queue2.popleft() levels1[level1][node1.val] += 1 if node1 else 0 levels2[level2][node2.val] += 1 if node2 else 0 if node1: queue1.append((node1.left, level1 + 1)) queue1.append((node1.right, level1 + 1)) if node2: queue2.append((node2.left, level2 + 1)) queue2.append((node2.right, level2 + 1)) return all(levels1[level] == levels2[level] for level in levels1) # Using the same example trees from Method 1 print(areLevelsAnagramsBFS(tree1, tree2))

The output of this code snippet:

True

Here, we use a `Counter`

in conjunction with a breadth-first search, leveraging the `deque`

for enqueuing tuples of nodes and their respective levels. Each level’s node values are counted, and the comparison of these counts between both trees determines if they are anagrams at every level.

## Bonus One-Liner Method 5: Using Zip and Map with Level Order Traversal

This is a condensed version, applying Python’s `zip`

and `map`

functions to achieve the same anagram level check. Implemented as a one-liner within `areLevelsAnagramsOneliner(tree1, tree2)`

.

Here’s an example:

def areLevelsAnagramsOneliner(tree1, tree2): return all(sorted(level1) == sorted(level2) for level1, level2 in zip(levelOrderTraversal(tree1), levelOrderTraversal(tree2))) # Using the same levelOrderTraversal implementation from Method 1 # Using the same example trees from Method 1 print(areLevelsAnagramsOneliner(tree1, tree2))

The output of this code snippet:

True

This one-liner uses Python’s `zip`

to pair up the levels between two trees and `map`

to apply the `sorted()`

function, making a concise and functional comparison of whether the levels are anagrams.

## Summary/Discussion

**Method 1:**Level Order Traversal and Sorting. Strengths: Easy to understand and implement. Weaknesses: Requires extra memory for storing levels and has a higher time complexity due to sorting.**Method 2:**Recursive Preorder Traversal. Strengths: Recursive method offers a natural way to traverse the tree structure. Weaknesses: Recursive function calls may lead to higher memory usage in the case of deep trees.**Method 3:**Hash Function-Based Verification. Strengths: Skips the need for sorting by using hash functions. Weaknesses: Collisions might yield false positives, though highly unlikely.**Method 4:**Breadth-First Search with Counter. Strengths: Efficient for level by level comparison. Weaknesses: Slightly more complex due to tracking two queues.**Method 5:**One-Liner. Strengths: Very concise and elegant. Weaknesses: Less readable for those not familiar with Python’s functional programming capabilities.

Emily Rosemary Collins is a tech enthusiast with a strong background in computer science, always staying up-to-date with the latest trends and innovations. Apart from her love for technology, Emily enjoys exploring the great outdoors, participating in local community events, and dedicating her free time to painting and photography. Her interests and passion for personal growth make her an engaging conversationalist and a reliable source of knowledge in the ever-evolving world of technology.