EasyBlind75TreeDFSBFS

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Examples

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

Both trees have the same structure and values.

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

One tree has a left child, the other has a right child.

Constraints

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

Approaches

Use BFS to traverse both trees level by level, comparing nodes.

CodeT: O(n) | S: O(n)
from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_same_tree(p, q):
    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

Recursively compare both trees node by node.

CodeT: O(n) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

Same recursive approach with short-circuit evaluation.

Diagram

p: 1->2,3 q: 1->2,3 Compare: 1==1, 2==2, None==None, 3==3 -> True
CodeT: O(n) | S: O(h)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_same_tree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    return (p.val == q.val and
            is_same_tree(p.left, q.left) and
            is_same_tree(p.right, q.right))

Complexity Comparison

BFS - Level Order
T: O(n)S: O(n)

Use BFS to traverse both trees level by level, comparing nodes.

DFS - Recursive
T: O(n)S: O(h)

Recursively compare both trees node by node.

DFS - Short Circuit
T: O(n)S: O(h)

Same recursive approach with short-circuit evaluation.

Common Mistakes

Not checking both null cases before comparing values

Forgetting that structural differences make trees not same

Not using short-circuit evaluation for efficiency

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems