5 Best Ways to Check if All Levels of Two Trees are Anagrams in Python

Rate this post

πŸ’‘ 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.