Same Tree — Solution in Python, Java & C++
Same Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem, asked at Amazon and Microsoft.
Same Tree is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Microsoft and Bloomberg interviews.
- Difficulty: Easy
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Microsoft, Bloomberg
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given the roots p and q of two binary trees. Return true if the two trees are identical — the same shape, with equal values in every corresponding node — and false otherwise.
Example 1
Input: p = [1,2,3], q = [1,2,3]
Output: true
Example 2
Input: p = [1,2], q = [1,null,2]
Output: false
Explanation: Both trees hold 1 and 2, but in `p` the 2 is a left child and in `q` a right child — the shapes differ.
Example 3
Input: p = [1,2,1], q = [1,1,2]
Output: false
Explanation: Same shape, but the left children hold 2 and 1.
Constraints
The number of nodes in both trees is in the range [0, 100]-10^4 <= Node.val <= 10^4
Hints for Same Tree
Hint 1
Two empty trees are identical; an empty tree and a non-empty one are not.
Hint 2
Two non-empty trees are identical exactly when their roots hold the same value and their left subtrees are identical and their right subtrees are identical.
Hint 3
That sentence is the whole recursion — compare, then recurse on the left pair and the right pair, stopping at the first mismatch.
How to solve Same Tree
Identity is defined recursively: equal roots, identical left subtrees, identical right subtrees. Walk both trees in lock-step and stop at the first difference in shape or value.
Approach
- If both nodes are null, return
true. - If exactly one is null, return
false— the shapes differ. - If the values differ, return
false. - Otherwise return
same(p.left, q.left) && same(p.right, q.right).
Why it works
Each call compares one pair of positions that occupy the same place in both trees. Every position present in either tree is reached, because the recursion only stops early on a mismatch (which already decides the answer) or when both sides are empty (nothing left to compare there).
Complexity
- Time —
O(min(n, m)) — the walk stops at the smaller tree's boundary or the first mismatch - Space —
O(h) recursion depth
Pitfalls
- Comparing one traversal list is not enough:
[1,2]and[1,null,2]have the same preorder[1,2]but different shapes. - Check the null cases before reading
.val.
Reference solution
Python
from typing import Optional
def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p is None or q is None:
return p is q
return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)Java
public static boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null || q == null) return p == q;
return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}C++
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p || !q) return p == q;
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}JavaScript
var isSameTree = function(p, q) {
if (p === null || q === null) return p === q;
return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)