Same 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
p = [1,2,3], q = [1,2,3]trueThe 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
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. This avoids unnecessary traversal of subtrees once inequality is found.
Optimal Approach
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. The conjunction of these recursive calls ensures structural and value equality throughout the trees.
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.
Pattern Spotlight
DFS (Recursive Tree Traversal)
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.
Solution
| 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)) |
| 1 | import java.util.*; |
| 2 | |
| 3 | class Solution { |
| 4 | public boolean isSameTree(TreeNode p, TreeNode q) { |
| 5 | if (p == null && q == null) { |
| 6 | return true; |
| 7 | } |
| 8 | if (p == null || q == null || p.val != q.val) { |
| 9 | return false; |
| 10 | } |
| 11 | |
| 12 | return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); |
| 13 | } |
| 14 | } |
| 1 | #include <iostream> |
| 2 | |
| 3 | using namespace std; |
| 4 | |
| 5 | class Solution { |
| 6 | public: |
| 7 | bool isSameTree(TreeNode* p, TreeNode* q) { |
| 8 | if (p == nullptr && q == nullptr) { |
| 9 | return true; |
| 10 | } |
| 11 | if (p == nullptr || q == nullptr || p->val != q->val) { |
| 12 | return false; |
| 13 | } |
| 14 | |
| 15 | return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); |
| 16 | } |
| 17 | }; |
| 1 | var isSameTree = function(p, q) { |
| 2 | if (p === null && q === null) { |
| 3 | return true; |
| 4 | } |
| 5 | if (p === null || q === null || p.val !== q.val) { |
| 6 | return false; |
| 7 | } |
| 8 | |
| 9 | return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); |
| 10 | }; |
Step-by-Step Solution
Return True if Both Nodes Are Null
| 3 | if 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.
Return False if One Node Is Null or Values Differ
| 5 | if not p or not q or p.val != q.val:
|
| 6 | return False
|
Objective
To detect structural or value mismatches early and prune the recursion.
Key Insight
If exactly one node is null, the trees differ in structure. If both nodes exist but their values differ, the trees differ in content. Returning false immediately avoids unnecessary traversal of subtrees that cannot be equal.
Interview Quick-Check
Core Logic
Checking for null mismatches or value inequality is the critical pruning condition that ensures correctness and efficiency.
Common Pitfalls & Bugs
Failing to check both null and value conditions can lead to incorrect equality results.
Recursively Verify Left and Right Subtrees
| 8 | return (self.isSameTree(p.left, q.left) and
|
| 9 | self.isSameTree(p.right, q.right)) |
Objective
To confirm that both left and right subtrees are identical by recursive DFS calls.
Key Insight
The conjunction of recursive calls on left and right children ensures that the entire tree structure and node values match. This leverages the natural recursive definition of tree equality and propagates mismatch detection up the call stack.
Interview Quick-Check
Core Logic
The recursive calls combine to verify full structural and value equality across both subtrees.
State & Boundaries
The use of logical AND ensures both subtrees must be identical for the current nodes to be considered equal.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
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.
return FalseReturn false if nodes differ in presence or value.
Returning false here prevents further unnecessary recursion and correctly signals that the trees are not identical.
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.
return TrueReturn true when both nodes are null.
Returning true here is essential because it signifies that corresponding branches have matched completely up to this point.
return (self.isSameTree(p.left, q.left) andRecursively check if left subtrees are identical and right subtrees are identical.
This recursive conjunction ensures that both subtrees must be identical for the current nodes to be considered equal, propagating the equality check throughout the entire tree.
self.isSameTree(p.right, q.right))Return the combined result of left and right subtree comparisons.
Returning the logical AND of both recursive calls ensures that any mismatch in either subtree causes the entire comparison to fail.
Test Your Understanding
Why does the algorithm return false immediately when one node is null and the other is not?
Because structural equality requires both nodes to be present or absent simultaneously; a mismatch in presence means the trees differ in shape, so they cannot be the same.
Related Problems
DFS pattern
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