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 3But the following is not:

1 / \ 2 2 \ \ 3 3Constraints

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.

#### Algorithms to Check if a Binary Tree is Symmetric

–EOF (The Ultimate Computing & Technology Blog) —

**GD Star Rating***loading…*

640 words

**Last Post**: Teaching Kids Programming – Algorithms to Find Minimum Common Value of Two Sorted Arrays (Binary Search, Two Pointer, Brute Force, Hash Set Intersection) **Next Post**: 5 Things to Look For in a WordPress Hosting Provider

Source: Internet