Same Tree

Difficulty: Easy | Acceptance: 67.10% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree

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.

• Examples
• Constraints
• Recursive Depth-First Search
• Iterative Depth-First Search
• Breadth-First Search

Examples

Example 1:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false

Constraints

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

Recursive Depth-First Search

Intuition We can solve this problem by recursively checking if the corresponding nodes in both trees have the same value and if their left and right subtrees are also identical.

Steps

• If both p and q are null, return true.
• If one of them is null or their values differ, return false.
• Recursively check the left children and the right children.

# 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:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Complexity

• Time: O(N) where N is the number of nodes in the smaller tree.
• Space: O(H) where H is the height of the tree, due to the recursion stack.
• Notes: In the worst case (skewed tree), space complexity is O(N).

Iterative Depth-First Search

Intuition We can simulate the recursive approach using an explicit stack data structure to avoid recursion stack overflow issues on very deep trees.

Steps

• Initialize a stack with pairs of nodes (p, q).
• While the stack is not empty, pop a pair.
• Check for null conditions and value equality.
• If valid, push the left children pair and right children pair onto the stack.

# 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:
        stack = [(p, q)]
        while stack:
            node1, node2 = stack.pop()
            if not node1 and not node2:
                continue
            if not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False
            stack.append((node1.right, node2.right))
            stack.append((node1.left, node2.left))
        return True

Complexity

• Time: O(N) where N is the number of nodes in the smaller tree.
• Space: O(H) where H is the height of the tree, for the stack.
• Notes: Iterative DFS avoids potential stack overflow errors in languages with strict recursion limits.

Breadth-First Search

Intuition We can traverse the trees level by level using a queue. At each step, we dequeue a pair of nodes and compare them.

Steps

• Initialize a queue with the pair (p, q).
• While the queue is not empty, dequeue a pair.
• Check for null conditions and value equality.
• If valid, enqueue the left children pair and right children pair.

from collections import deque

# 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:
        queue = deque([(p, q)])
        while queue:
            node1, node2 = queue.popleft()
            if not node1 and not node2:
                continue
            if not node1 or not node2:
                return False
            if node1.val != node2.val:
                return False
            queue.append((node1.left, node2.left))
            queue.append((node1.right, node2.right))
        return True

Complexity

• Time: O(N) where N is the number of nodes in the smaller tree.
• Space: O(W) where W is the maximum width of the tree.
• Notes: In the worst case (a complete binary tree), the maximum width can be up to N/2.