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

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.

Algorithms to Check if a Binary Tree is Symmetric

• Teaching Kids Programming – Iterative Algorithm to Check if a Binary Tree is Symmetric
• Teaching Kids Programming – Revisit the Symmetric Binary Tree by Using Clone and Invert Algorithm
• Teaching Kids Programming – Recursive Algorithm to Determine if a Binary Tree is Symmetric
• How to Check Symmetric Tree in C++ (Iterative and Recursion)?

–EOF (The Ultimate Computing & Technology Blog) —