Same Tree
Description
Given the roots of two binary trees p and q, write a function to determine whether they are the same tree.
Two binary trees are considered the same if and only if:
- They are structurally identical — every node in one tree has a corresponding node in the other at the same position.
- Every pair of corresponding nodes has the same value.
In other words, if you were to overlay one tree on top of the other, every node would match perfectly in both position and value.
Examples
Example 1
Input: p = [1, 2, 3], q = [1, 2, 3]
Output: true
Explanation: Both trees have the same structure: root 1 with left child 2 and right child 3. Every corresponding node has the same value (1==1, 2==2, 3==3), so the trees are identical.
Example 2
Input: p = [1, 2], q = [1, null, 2]
Output: false
Explanation: Tree p has root 1 with a left child 2 (no right child). Tree q has root 1 with a right child 2 (no left child). Even though both trees contain the same values {1, 2}, the structure is different — in p the 2 is on the left, in q it is on the right. Since the structure does not match, the trees are not the same.
Example 3
Input: p = [1, 2, 1], q = [1, 1, 2]
Output: false
Explanation: Both trees have the same structure (root with two children), but the values at corresponding positions differ. In tree p, the left child is 2 and the right child is 1. In tree q, the left child is 1 and the right child is 2. Since corresponding node values do not match (left: 2 ≠ 1), the trees are not the same.
Constraints
- 0 ≤ Number of nodes in both trees ≤ 100
- -10^4 ≤ Node.val ≤ 10^4
Editorial
Brute Force
Intuition
A straightforward way to check if two trees are identical is to convert each tree into a string representation and then compare the two strings. If both trees produce the exact same string, they must have the same structure and the same values at every position.
We can serialize each tree using a preorder traversal (root, left, right), encoding null children explicitly as a special marker (like "#") so that the structure is fully captured. Two trees with different structures will produce different strings because the null markers will appear at different positions.
Think of it like taking a photograph of each tree from the same angle. If the two photographs look identical pixel by pixel, the trees are the same. The serialization is our "photograph" — it captures every detail of the tree's shape and content.
Step-by-Step Explanation
Let's trace through with p = [1, 2, 3] and q = [1, 2, 3] (Example 1):
Tree p:
1
/ \
2 3
Tree q:
1
/ \
2 3
Step 1: Serialize tree p using preorder traversal.
- Visit root 1: result = "1"
- Go left to 2: result = "1,2"
- Node 2 has no left child: result = "1,2,#"
- Node 2 has no right child: result = "1,2,#,#"
- Go right to 3: result = "1,2,#,#,3"
- Node 3 has no left child: result = "1,2,#,#,3,#"
- Node 3 has no right child: result = "1,2,#,#,3,#,#"
Step 2: Serialize tree q using the same method.
- Following the same traversal: result = "1,2,#,#,3,#,#"
Step 3: Compare the two serialized strings.
- "1,2,#,#,3,#,#" == "1,2,#,#,3,#,#"? YES
Result: Return true — the trees are identical.
Now let's also consider Example 2: p = [1, 2] and q = [1, null, 2]
Step 4: Serialize tree p: "1,2,#,#,#"
- Root 1, left child 2 (with null children), no right child.
Step 5: Serialize tree q: "1,#,2,#,#"
- Root 1, no left child, right child 2 (with null children).
Step 6: Compare: "1,2,#,#,#" vs "1,#,2,#,#" — NOT equal.
Result: Return false — different structures produce different serializations.
Brute Force — Serialize and Compare Tree p — Watch how preorder traversal with null markers creates a unique string fingerprint of the tree structure.
Algorithm
- Define a serialize function that takes a tree root and returns a string:
a. If the node is null, return "#"
b. Otherwise, return node.val + "," + serialize(left) + "," + serialize(right) - Serialize both trees p and q
- Compare the two resulting strings
- If they are equal, return true; otherwise, return false
Code
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
string serialize(TreeNode* node) {
if (!node) return "#";
return to_string(node->val) + "," + serialize(node->left) + "," + serialize(node->right);
}
bool isSameTree(TreeNode* p, TreeNode* q) {
return serialize(p) == serialize(q);
}
};# 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: TreeNode, q: TreeNode) -> bool:
def serialize(node):
if not node:
return "#"
return str(node.val) + "," + serialize(node.left) + "," + serialize(node.right)
return serialize(p) == serialize(q)/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int val) { this.val = val; }
* }
*/
class Solution {
private String serialize(TreeNode node) {
if (node == null) return "#";
return node.val + "," + serialize(node.left) + "," + serialize(node.right);
}
public boolean isSameTree(TreeNode p, TreeNode q) {
return serialize(p).equals(serialize(q));
}
}Complexity Analysis
Time Complexity: O(n)
We visit every node in both trees once during serialization. Each node contributes a constant amount of work (appending its value to the string). The string comparison at the end is also O(n) in the length of the serialized strings. Total: O(n) where n is the number of nodes in the larger tree.
Space Complexity: O(n)
We build two serialized strings, each of size proportional to the number of nodes (each node contributes its value and null markers). Additionally, the recursion stack uses O(h) space where h is the tree height. The dominant term is the O(n) string storage.
This is wasteful because we always traverse both entire trees even if the very first nodes differ. We also allocate O(n) extra space for the strings when we could compare on the fly.
Why This Approach Is Not Efficient
The serialization approach has two key inefficiencies:
-
Unnecessary full traversal: Even if the two trees differ at the very first node (roots have different values), we still serialize both entire trees before comparing. For large trees, this means doing O(n) work when O(1) would have been enough to determine they are different.
-
Extra O(n) space for strings: We allocate two strings proportional to the tree size just to compare them. This is wasteful when we could compare nodes directly during traversal, using only O(h) stack space.
The key insight is: we do not need to build a complete representation of each tree. We can compare corresponding nodes simultaneously as we traverse both trees. The moment we find a mismatch — either in structure (one node is null and the other is not) or in value (both nodes exist but have different values) — we can immediately return false without looking at the rest.
Optimal Approach - Recursive DFS Comparison
Intuition
Instead of serializing both trees and comparing the result, we can compare the two trees node by node simultaneously using recursion. At each step, we look at the current node from tree p and the current node from tree q at the same position.
There are exactly four possible scenarios at each pair of corresponding positions:
- Both nodes are null: This pair matches — we have reached the end of both subtrees at the same point. Return true.
- One node is null, the other is not: The structure differs at this position. Return false immediately.
- Both nodes exist but have different values: The values differ. Return false immediately.
- Both nodes exist and have the same value: So far so good — but we need to check that both their left subtrees match AND both their right subtrees match. Recurse on both pairs.
The tree is the same only if ALL recursive calls return true. A single false anywhere means the trees are different.
Think of it like comparing two family trees side by side. You start at the top (the two roots). If both have the same name, you then compare their first children, and then their second children, and so on. If at any point the names differ or one has a child where the other does not, the trees are different.
Step-by-Step Explanation
Let's trace through with p = [1, 2, 1] and q = [1, 1, 2] (Example 3):
Tree p:
1
/ \
2 1
Tree q:
1
/ \
1 2
Step 1: Compare roots: p.val = 1, q.val = 1.
- Both exist and values match (1 == 1). Continue to subtrees.
Step 2: Compare left children: p.left.val = 2, q.left.val = 1.
- Both exist, but values differ (2 ≠ 1).
- Mismatch found! Return false immediately.
Step 3: Since the left subtree comparison returned false, the overall result is false. We never even need to compare the right subtrees.
Result: Return false.
Now let's also trace the matching case: p = [1, 2, 3], q = [1, 2, 3] (Example 1):
Step 4: Compare roots: p.val = 1, q.val = 1 → match ✓.
Step 5: Compare left children: p.left.val = 2, q.left.val = 2 → match ✓.
Step 6: Compare left-left: p.left.left = null, q.left.left = null → both null, match ✓.
Step 7: Compare left-right: p.left.right = null, q.left.right = null → both null, match ✓.
Step 8: Compare right children: p.right.val = 3, q.right.val = 3 → match ✓.
Step 9: Compare right-left: null, null → match ✓.
Step 10: Compare right-right: null, null → match ✓.
Result: All comparisons passed. Return true.
Recursive DFS — Simultaneous Tree Comparison — Watch how we compare corresponding nodes from both trees simultaneously, catching the value mismatch at the left children and returning false early.
Algorithm
- If both p and q are null, return true (two empty trees are the same)
- If exactly one of p or q is null, return false (structural mismatch)
- If p.val ≠ q.val, return false (value mismatch)
- Recursively check:
- isSameTree(p.left, q.left) — left subtrees must match
- isSameTree(p.right, q.right) — right subtrees must match
- Return true only if both recursive calls return true
Code
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
// Both nodes are null — same structure at this position
if (!p && !q) return true;
// One is null, the other is not — structural mismatch
if (!p || !q) return false;
// Values differ at this position
if (p->val != q->val) return false;
// Both exist with same value — check subtrees
return isSameTree(p->left, q->left) &&
isSameTree(p->right, q->right);
}
};class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
# Both nodes are null — same structure at this position
if not p and not q:
return True
# One is null, the other is not — structural mismatch
if not p or not q:
return False
# Values differ at this position
if p.val != q.val:
return False
# Both exist with same value — check subtrees
return (self.isSameTree(p.left, q.left) and
self.isSameTree(p.right, q.right))class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// Both nodes are null — same structure at this position
if (p == null && q == null) return true;
// One is null, the other is not — structural mismatch
if (p == null || q == null) return false;
// Values differ at this position
if (p.val != q.val) return false;
// Both exist with same value — check subtrees
return isSameTree(p.left, q.left) &&
isSameTree(p.right, q.right);
}
}Complexity Analysis
Time Complexity: O(n)
In the worst case (both trees are identical), we visit every node in both trees once. Each node visit involves a constant-time value comparison. In the best case (roots differ), we return in O(1). On average, we may short-circuit as soon as a mismatch is found, potentially checking far fewer than all n nodes.
Space Complexity: O(h)
The only space used is the recursion call stack, proportional to the height h of the trees. For balanced trees, h = O(log n). For completely skewed trees (like a linked list), h = O(n). No additional data structures are allocated — no strings, no arrays. This is a significant improvement over the O(n) space used by the serialization approach.