Log inSign up
easyleetcodeNot Started

Same Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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.

Example 1 · Example 1: Identical Trees:

Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Explanation: Both trees have the same structure and node values.

Example 2 · Example 2: Different Structures:

Input: p = [1, 2], q = [1, null, 2]
Output: false
Explanation: In p, 2 is a left child; in q, 2 is a right child.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Formulate simultaneous dual-tree recursive traversal.
  • Handle null pointer mismatch checks cleanly.
  • Understand early pruning on mismatch.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Compare two binary trees for exact structural and value equality.
  • Simultaneous twin traversal.

Algorithmic Decision Tree:

  • if (!p && !q) return true;
  • if (!p || !q || p.val != q.val) return false;
  • return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);

Connected Patterns:

Symmetric TreeSubtree of Another TreeInvert Binary Tree

1. Tree Serialization and Comparison

Intuition

Serialize p and q using preorder traversal with # for nulls, then compare strings.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Serialize tree p to string s1.
  2. Step 2: Serialize tree q to string s2.
  3. Step 3: Return s1 == s2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 void serialize(TreeNode* root, string& s) {
10 if (!root) { s += "#,"; return; }
11 s += to_string(root->val) + ",";
12 serialize(root->left, s);
13 serialize(root->right, s);
14 }
15 bool isSameTree(TreeNode* p, TreeNode* q) {
16 string s1 = "", s2 = "";
17 serialize(p, s1);
18 serialize(q, s2);
19 return s1 == s2;
20 }
21};
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n + m) — Builds full string serialization of both trees.
  • Space complexity: O(n + m) — String memory O(n + m).

2. Iterative Queue BFS Pair Traversal

Intuition

Push {p, q} into queue. Pop {n1, n2}. If both null, continue. If one null or n1.val != n2.val, return false. Push {n1.left, n2.left} and {n1.right, n2.right}.

When to apply: When avoiding recursive call stacks.

Algorithm

  1. Step 1: Initialize queue q, push {p, q}.
  2. Step 2: While queue is not empty:
  3. - Pop {n1, n2}.
  4. - If !n1 && !n2: continue.
  5. - If !n1 || !n2 || n1.val != n2.val: return false.
  6. - Push {n1.left, n2.left}, {n1.right, n2.right}.
  7. Step 3: Return true.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isSameTree(TreeNode* p, TreeNode* q) {
10 queue<pair<TreeNode*, TreeNode*>> que;
11 que.push({p, q});
12 while (!que.empty()) {
13 auto [n1, n2] = que.front();
14 que.pop();
15 if (!n1 && !n2) continue;
16 if (!n1 || !n2 || n1->val != n2->val) return false;
17 que.push({n1->left, n2->left});
18 que.push({n1->right, n2->right});
19 }
20 return true;
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(min(n, m)) — Terminates early on first mismatch or completes in O(min(n, m)).
  • Space complexity: O(min(w1, w2)) — Queue stores nodes proportional to tree width.

3. Simultaneous Recursive DFS

Intuition

If both p and q are null, return true. If one is null or values differ, return false. Otherwise return isSameTree(p.left, q.left) && isSameTree(p.right, q.right).

When to apply: Standard optimal solution in all interviews.

Algorithm

  1. Step 1: If p == null && q == null return true.
  2. Step 2: If p == null || q == null || p.val != q.val return false.
  3. Step 3: Return isSameTree(p.left, q.left) && isSameTree(p.right, q.right).

Same Tree Trace for p = [1, 2], q = [1, 2]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Compare roots: p
Visual state
Values and pointers at this exact step
tree
p Root
1
p Left
2

Node order shown; add connections to display explicit tree edges.

p_curr: 1
Check / comparison
p.val (1) == q.val (1)
Decision / next transition
Match. Check left subtrees.
Why this step matters

Step 1: Compare roots: p.val=1 == q.val=1. Match! Recurse on left children.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 bool isSameTree(TreeNode* p, TreeNode* q) {
10 if (!p && !q) return true;
11 if (!p || !q || p->val != q->val) return false;
12 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
13 }
14};
15
16int main() {
17 // Sample driver execution
18 cout << "Execution completed successfully." << endl;
19 return 0;
20}
21

Time & Space Complexity

  • Time complexity: O(min(n, m)) — Visits at most min(n, m) nodes, stopping immediately on first mismatch.
  • Space complexity: O(min(h1, h2)) — Call stack depth is bounded by min height.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.String SerializationO(n + m)O(n + m)Compare serialized string representation.String memory.
2.Iterative BFSO(min(n, m))O(w)Queue holds pairs of corresponding nodes.Queue memory.
3.Simultaneous Recursive DFSOptimalO(min(n, m))O(h)Direct 3-line structural recurrence.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Both trees empty: p = [], q = [] -> returns true.
  • One tree empty, one non-empty -> returns false.
  • Same values but mirror structures -> returns false.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Show how short-circuit evaluation in isSameTree(left) && isSameTree(right) stops immediately on the first mismatch.
  2. Discuss the iterative alternative using a single Queue holding pairs of nodes.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why must the base case check if (!p && !q) BEFORE checking if (!p || !q)?

Back to DSA Sheet