# Teaching Kids Programming – Iterative Algorithm to Check if a Binary Tree is Symmetric

Teaching Kids Programming – Iterative Algorithm to Check if a Binary Tree is Symmetric | ninjasquad

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root to a binary tree root, return whether it is symmetric.

For example, this binary tree is symmetric:

```    1
/ \
2   2
/ \ / \
3  4 4  3```

But the following is not:

```    1
/ \
2   2
\   \
3    3```

Constraints
n ≤ 100,000 where n is the number of nodes in root

### Iterative Algorithm to Check if a Binary Tree is Symmetric

We can traverse the binary tree in any order e.g. Breadth First Search algorithm via level by level order, or Depth First Search via stack. We push a pair of root nodes, and then start comparing them, and push their corresponding symmetric nodes e.g. left and right, right and left.

The algorithm should return False immediately if the node and corresponding node does not match. Please note that if we push corresponding left tree and left tree, right tree and right tree, which virtually becomes the algorithm to check if two trees are identical.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ``` ```# 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 class Solution:     def isSymmetric(self, root: Optional[TreeNode]) -> bool:         q = [(root, root)] # or using a queue e.g. deque is fine         while q:             a, b = q.pop()             if a is None and b is None:                 continue             elif a is None or b is None:                 return False             elif a.val != b.val:                 return False             q.append((a.left, b.right))             q.append((a.right, b.left))         return True```
```# 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
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
q = [(root, root)] # or using a queue e.g. deque is fine
while q:
a, b = q.pop()
if a is None and b is None:
continue
elif a is None or b is None:
return False
elif a.val != b.val:
return False
q.append((a.left, b.right))
q.append((a.right, b.left))
return True```

The time/space complexity is O(N) where N is the number of the nodes in the binary tree. The binary tree may be degraded into a singly list or Zizag shape where each node has only one child node.

GD Star Rating