What pattern does Same Tree use?

The Pattern: DFS (Recursive Tree Traversal) The Heuristic: When comparing two trees for structural and value equality, recursively check corresponding nodes and prune immediately upon mismatch, leveraging the natural recursive structure of trees for clean and efficient traversal.

Same Tree — DFS | AlgoDrill

Q: What is the time complexity of Same Tree?

O(n). Each node in both trees is visited at most once. The recursion stops early if a mismatch is found, but in the worst case all nodes are compared, where n is the number of nodes in the smaller tree.

Problem

Given the roots of two binary trees p and q, return true if they are the same or false otherwise. Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

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

Example

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

Output: true

The algorithm recursively compares nodes starting from the roots. At the root, both have value 1, so it proceeds to compare left children: both have value 2, so it recurses further. Then it compares right children: both have value 3. Since all corresponding nodes match in value and structure, the function returns true. If at any point the nodes differ in value or structure (one is null while the other is not), the function returns false immediately, pruning the search.

Approach

Straightforward Solution

A brute-force approach would traverse both trees simultaneously, comparing nodes one by one. This is already optimal since every node must be checked to confirm equality.

Core Observation

Two trees are the same if their roots have the same value and their left and right subtrees are also the same. This naturally suggests a recursive approach that checks node equality and recurses on children.

Path to Optimal

Preview

The problem's recursive structure aligns perfectly with a Depth-First Search (DFS) traversal. The key insight is to return false immediately upon detecting any mismatch in node presence or value, enabling early pruning…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a recursive DFS function that returns true if both nodes are null, false if only one is null or their values differ, and otherwise recursively checks the left and right children…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each node in both trees is visited at most once. The recursion stops early if a mismatch is found, but in the worst case all nodes are compared, where n is the number of nodes in the smaller tree.

Space

O(h)

The recursion stack depth is proportional to the height h of the trees. In the worst case of a skewed tree, this can be O(n), but for balanced trees it is O(log n). This is auxiliary space excluding input storage.

Solution

Python

1class Solution:
  def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
      if not p and not q:
          return True
      if not p or not q or p.val != q.val:
          return False
      
      return (self.isSameTree(p.left, q.left) and
              self.isSameTree(p.right, q.right))

Step-by-Step Solution

1

Return True if Both Nodes Are Null

3if not p and not q:
4    return True

Objective

To handle the base case where both nodes are null, indicating identical empty subtrees.

Key Insight

If both nodes are null, they are trivially equal. This base case stops recursion and confirms that corresponding branches match structurally and in value (since they are absent).

Interview Quick-Check

Core Logic

Returning true when both nodes are null ensures the recursion correctly identifies matching leaf endpoints.

State & Boundaries

This base case prevents further recursion into non-existent children.

2

Return False if One Node Is Null or Values Differ

To detect structural or value mismatches early and prune the recursion.

3

Recursively Verify Left and Right Subtrees

To confirm that both left and right subtrees are identical by recursive DFS calls.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 6 Critical lines interviewers watch for.

Line 5 Critical

if not p or not q or p.val != q.val:

Check if either node is null or if their values differ.

This condition detects any structural or value mismatch immediately, enabling early pruning of the recursion and ensuring correctness.

Line 6 Critical

return False

Return false if nodes differ in presence or value.

Returning false here prevents further unnecessary recursion and correctly signals that the trees are not identical.

Line 3 Critical

if not p and not q:

Check if both nodes p and q are null.

This base case confirms that two empty subtrees are identical, allowing recursion to terminate successfully at leaf nodes.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does the algorithm return false immediately when one node is null and the other is not?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Same Tree from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Same Tree drill

or drill a free problem

1	`class Solution:`
2	`def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:`
3	`if not p and not q:`
4	`return True`
5	`if not p or not q or p.val != q.val:`
6	`return False`
7
8	`return (self.isSameTree(p.left, q.left) and`
9	`self.isSameTree(p.right, q.right))`