5 Best Ways to Check Whether a Given Tree is Symmetric in Python

by

💡 Problem Formulation: A Symmetric Tree, also known as a Mirror Tree, is a binary tree in which the left subtree is a mirror reflection of the right subtree. In this article, we will explore methods to determine if a given binary tree is symmetric. For instance, a binary tree with elements [1, 2, 2, 3, 4, 4, 3] should be identified as symmetric.

Method 1: Recursive Approach

The recursive approach is a straightforward method that compares the left and right subtrees in a recursive fashion. Two nodes are symmetric if their values are equal, and the right subtree of each node is a mirror reflection of the left subtree of the other node.

Here’s an example:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
        
def isMirror(t1, t2):
    if not t1 and not t2:
        return True
    if not t1 or not t2:
        return False
    return (t1.val == t2.val) and isMirror(t1.right, t2.left) and isMirror(t1.left, t2.right)
    
def isSymmetric(root):
    return isMirror(root, root)

# Example Tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)

print(isSymmetric(root))

Output: True

This code snippet defines a TreeNode class to represent each node in the tree. It then utilizes helper function isMirror to recursively compare corresponding nodes in the two subtrees.

Method 2: Iterative Approach

The iterative approach emulates the recursive process using a queue. Each pair of nodes to be compared is placed in the queue, and the comparison is performed in a loop until the queue is empty.

Here’s an example:

from collections import deque

def isSymmetric(root):
    if not root:
        return True
    queue = deque([(root.left, root.right)])
    while queue:
        t1, t2 = queue.popleft()
        if not t1 and not t2:
            continue
        if not t1 or not t2:
            return False
        if t1.val != t2.val:
            return False
        queue.append((t1.left, t2.right))
        queue.append((t1.right, t2.left))
    return True

# Example usage with the same tree structure as above
print(isSymmetric(root))

Output: True

This code example uses a queue to iteratively check pairs of nodes for symmetry, stopping and returning False if any asymmetry is detected, otherwise returning True once all pairs have been checked.

Method 3: Level-Order Traversal

This method involves performing a level-order traversal of the tree using a queue and checking if each level of the tree is a palindrome, indicating it is symmetric.

Here’s an example:

from collections import deque

def isSymmetric(root):
    if not root:
        return True
    queue = deque([root])
    while queue:
        level = []
        level_length = len(queue)
        for _ in range(level_length):
            node = queue.popleft()
            if node:
                level.append(node.val)
                queue.append(node.left)
                queue.append(node.right)
            else:
                level.append(None)
        if level != level[::-1]:
            return False
    return True

Output: True

This code conducts a level-order traversal and uses list slicing to determine if the current level list is equal to its reverse, which would mean the level is symmetrical.

Method 4: Depth-First Search (DFS)

Using Depth-First Search (DFS), this method visits each branch and follows it to the end before backtracking, thereby checking symmetric properties for each sub-tree in a depth-first manner.

Here’s an example:

def isSymmetric(root):
    def dfs(node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2:
            return False
        if node1.val != node2.val:
            return False
        return dfs(node1.left, node2.right) and dfs(node1.right, node2.left)
    
    return dfs(root, root)

# Same example tree and usage.
print(isSymmetric(root))

Output: True

This code uses a DFS approach to explore each branch of the tree to the fullest extent before backtracking, ensuring the left and right sub-trees mirror each other.

Bonus One-Liner Method 5: Using Built-in Functions

For those seeking a highly concise solution, Python’s built-in functions can be leveraged to write a one-liner that checks if a tree is symmetric. This leverages methods 1-4, encapsulating the logic in a lambda expression.

Here’s an example:

isSymmetric = lambda root: (lambda f, r: f(r, r))(lambda t1, t2: t1 is t2 or (t1 and t2 and t1.val == t2.val and f(t1.left, t2.right) and f(t1.right, t2.left)), root)

# Same example tree and usage.
print(isSymmetric(root))

Output: True

This single-line function uses a lambda expression to create an isomorphic behavior to a recursive function, efficiently checking the mirror symmetry of a tree.

Summary/Discussion

  • Method 1: Recursive Approach. Intuitive and elegant. Might suffer from stack overflow for very deep trees.
  • Method 2: Iterative Approach. Uses a queue to avoid the pitfalls of deep recursion. May be slightly less intuitive but is more space efficient for broad trees.
  • Method 3: Level-Order Traversal. Directly verifies symmetry at each level, thus is easy to understand. However, can be less efficient as it builds an extra list for each level.
  • Method 4: Depth-First Search (DFS). Space efficient and logically clear, but also prone to stack overflow with deep trees.
  • Bonus Method 5: Using Built-in Functions. Extremely succinct, but can be difficult to read and understand for those not well-versed in Python or functional programming concepts.