How to Solve Same Tree

To solve Same Tree, recursively or iteratively traverse both trees simultaneously, comparing node values and structure. DFS allows deep comparison with stack or recursion, while BFS uses queues for level-order validation. The process ensures early termination on mismatch, guaranteeing correct identification of identical or differing trees.

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

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.

How GhostInterview Helps

• Capture input trees via screenshot or input layer for direct evaluation.
• Trace the answer path using recursive or iterative DFS/BFS and explain time and space complexity per method.
• Support screen-share workflows showing node-by-node comparison, highlighting differences or confirming identical structure.

Topic Pages

• Tree
• Depth-First Search
• Breadth-First Search
• Binary Tree

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.