**π‘ 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.