Teaching Kids Programming – Breadth First Search Algorithm to Check If Two Binary Trees are Same

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Compare Two Binary Trees for Equality using Breadth First Search Algorithm

Despite we can use Depth First Search Algorithm (Recursion) to check two binary trees for equality, we can also use Breadth First Search Algorithm to perform the tree equality checks.

We push a pair of the nodes from both trees (same position), and fail if immediately we find mismatch. Otherwise, we continue pushing the corresponding left, and right trees to the queue.

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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        q = deque([(p, q)])
        while q:
            a, b = q.popleft()
            if a is None and b is None:
                continue
            if a is None or b is None:
                return False
            if a.val != b.val:
                return False
            q.append((a.left, b.left))
            q.append((a.right, b.right))
        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 isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        q = deque([(p, q)])
        while q:
            a, b = q.popleft()
            if a is None and b is None:
                continue
            if a is None or b is None:
                return False
            if a.val != b.val:
                return False
            q.append((a.left, b.left))
            q.append((a.right, b.right))
        return True

The time complexity and space complexity is O(Min(N, M)) where N and M are the number of the nodes from both binary trees respectively.

Same Binary Tree Check Algorithm:

• How to Check If Two Binary Trees are the Same?
• Teaching Kids Programming – Recursive Depth First Search Algorithm to Check If Two Binary Trees are Same
• GoLang: Check Same Binary Trees via DFS or BFS Algorithms
• Teaching Kids Programming – Breadth First Search Algorithm to Check If Two Binary Trees are Same

–EOF (The Ultimate Computing & Technology Blog) —