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

Rate this post

π‘ 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.