deepSWE.io

Same Tree

TreeDFSRecursion

5 min

Problem Statement

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.

Example

Example 1:

p: [1,2,3]

q: [1,2,3]

Output: true

Constraints

The number of nodes in both trees is in the range [0, 100].
-10⁴ ≤ Node.val ≤ 10⁴

Recursive Solution (DFS)

The recursive approach uses a Depth-First Search (DFS) strategy to traverse both trees simultaneously and compare their nodes at each level.

Algorithm Steps

If both nodes are null, they are the same, so return true.
If one of the nodes is null or their values are different, they are not the same, so return false.
Recursively call the function on the left children and the right children.
Return true only if both the left and right subtrees are the same.

Start: Call isSameTree on roots p(1) and q(1).

Same Tree Solution


# 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: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # If both nodes are null, they are the same
        if not p and not q:
            return True
        # If one of the nodes is null or their values are different, they are not the same
        if not p or not q or p.val != q.val:
            return False
        
        # Recursively check the left and right subtrees
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Iterative Solution (BFS with Queue)

The iterative solution uses a queue to perform a Breadth-First Search (BFS). We add nodes from both trees to the queue and compare them at each step.

Algorithm Steps

Create a queue and add the root nodes of both trees.
While the queue is not empty, dequeue two nodes.
If both nodes are null, continue to the next iteration.
If one of the nodes is null or their values are different, the trees are not the same, so return false.
Add the left children of both nodes to the queue.
Add the right children of both nodes to the queue.
If the loop completes, the trees are the same, so return true.

Same Tree Solution


# 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
from collections import deque

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        queue = deque([(p, q)])
        
        while queue:
            node1, node2 = queue.popleft()
            
            if not node1 and not node2:
                continue
            if not node1 or not node2 or node1.val != node2.val:
                return False
                
            queue.append((node1.left, node2.left))
            queue.append((node1.right, node2.right))
            
        return True