Symmetric Tree

TreeRecursionDFSBFS

# Definition for a Binary Tree Node

``````class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
``````
1
2
3
4
5

# Solution

Both solutions take linear time and space.

# Recursion

Two trees are mirrors of each other if:

• the two roots have the same value
• the right subtree of each tree is a mirror reflection of the left subtree of the other tree
``````def mirror(self, t1: TreeNode, t2: TreeNode) -> bool:
if not t1 and not t2:
return True
elif not t1 or not t2:
return False
else:
return t1.val == t2.val\
and self.mirror(t1.left, t2.right)\
and self.mirror(t1.right, t2.left)

def isSymmetric(self, root: TreeNode) -> bool:
return self.mirror(root, root)
``````
1
2
3
4
5
6
7
8
9
10
11
12

# Iteration

The following code follows a BFS order to traverse the binary tree, but `queue.pop()` (DFS order) also works.

``````def isSymmetric(self, root: TreeNode) -> bool:
queue = []
queue.append(root)
queue.append(root)
while queue:
t1 = queue.pop(0)
t2 = queue.pop(0)
if not t1 and not t2:
continue
elif not t1 or not t2:
return False
elif t1.val != t2.val:
return False
else:
queue.append(t1.left)
queue.append(t2.right)
queue.append(t1.right)
queue.append(t2.left)
return True
``````
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19