#100

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Same Tree

Check whether two binary trees are identical by comparing structure and node values using DFS or BFS traversal strategies efficiently.

tree depth first search breadth first search binary tree

Problem Statement

Given the roots of two binary trees, p and q, implement a function to determine if they are exactly the same. Two trees are the same when they share identical structure and every corresponding node holds the same value. Consider using either depth-first or breadth-first traversal to verify each node efficiently, ensuring early exit when differences appear.

Your function should handle trees with up to 100 nodes and node values between -10^4 and 10^4. Examples include p = [1,2,3] and q = [1,2,3] returning true, or p = [1,2] and q = [1,null,2] returning false. The solution should carefully traverse both trees simultaneously, maintaining consistent state tracking for accurate comparison.

Examples

Example 1

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

Output: true

Example details omitted.

Example 2

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

Output: false

Example details omitted.

Example 3

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

Output: false

Example details omitted.

Constraints

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

Solution Approach

Recursive Depth-First Search

Use a recursive DFS approach by visiting both trees’ nodes simultaneously. At each recursion step, check if both nodes are null to continue, or if only one is null to return false immediately. Compare the node values and recursively check left and right subtrees. This approach directly maps to the binary-tree traversal pattern and allows natural short-circuiting on mismatch while maintaining simple, clear logic.

Iterative Depth-First Search Using a Stack

Simulate the recursive DFS using an explicit stack to avoid recursion limits. Push node pairs from both trees onto the stack, then iteratively pop and compare them. If node values differ or one node is null while the other isn’t, return false. Otherwise, push their children in order to the stack. This maintains state tracking explicitly and handles large trees without hitting call stack limits.

Breadth-First Search Using a Queue

Implement BFS with a queue by enqueueing node pairs from both trees. Dequeue nodes in pairs, check their values, and enqueue left and right children for both trees. Return false immediately on any structural or value mismatch. BFS provides level-by-level validation, useful when trees are wide, and ensures consistent comparison across levels while preserving traversal state accurately.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n), where n is the total number of nodes, because every node is visited once during DFS or BFS. Space complexity is O(h) for DFS recursion or stack, where h is tree height, and O(w) for BFS queue, where w is maximum tree width. These complexities align with the chosen traversal method and the need to track corresponding nodes.

What Interviewers Usually Probe

Do you account for null nodes when comparing two trees?
Can you implement both DFS and BFS to validate the trees efficiently?
Will you handle early termination when a mismatch is detected to optimize runtime?

Common Pitfalls or Variants

Common pitfalls

Failing to check for null nodes on only one side leading to incorrect true result.
Comparing node values without ensuring structural alignment can return false negatives.
Using BFS without properly enqueuing null children may skip necessary comparisons.

Follow-up variants

Check if one tree is a subtree of another while preserving structure and values.
Determine if two n-ary trees are identical using modified traversal logic.
Compare two trees to see if they are mirrors of each other rather than identical.

FAQ

What is the easiest way to compare two binary trees for Same Tree?

Use recursive DFS to simultaneously traverse both trees, checking nullity and node values. Early return on mismatch ensures efficient comparison.

Can BFS be used instead of DFS for this problem?

Yes, BFS with a queue can traverse trees level by level, comparing node pairs at each step while maintaining state tracking for correct validation.

What edge cases should I consider for Same Tree?

Include empty trees, trees with single nodes, and trees with differing structures but same node values to ensure accurate function behavior.

Why is state tracking important in this problem?

Tracking pairs of corresponding nodes ensures structural and value comparisons are synchronized. Without it, mismatches can be missed or incorrectly reported.

How does node value range affect the solution?

Node values from -10^4 to 10^4 do not affect traversal logic but confirm that integer comparisons are sufficient and no special handling for extreme values is needed.

terminal

Solution

Solution 1: DFS

We can use the DFS recursive method to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Solution 2: BFS

We can also use the BFS iterative method to solve this problem.

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#101 symmetric tree #104 maximum depth of binary tree #111 minimum depth of binary tree