Same Tree (LeetCode 100)
Two binary trees are given by their root nodes, p and q. Either tree may be empty. The trees are the same when they have the same shape and, at every position, the two nodes hold the same value.
Same shape means that wherever one tree has a left child, the other tree has a left child too, and the same for right children. Return True when the trees are the same and False otherwise.
Worked Examples
p = [1,2,3], q = [1,2,3]truep = [1,2], q = [1,null,2]falsep and the right child in q. The shapes differ.p = [1,2,1], q = [1,1,2]false⚖️Formal Constraints & Bounds
The number of nodes in both trees is in the range
[0, 100].-104 <= Node.val <= 104
Core Insight
Walk both trees at once and pair the children by position. A pair with one missing node means the shapes differ, so the answer is False. A pair of present nodes is the same when the values are equal and both child pairs are the same.
Real-World Scenario & Production Applications
A tool that compares two parsed documents, or two syntax trees of a program, walks both trees together and stops at the first position where they differ. A test that checks an expected nested document against an actual one does the same: it pairs the entries at each position and reports where the two disagree.
Step-by-Step Execution Trace Table
Example 2, p = [1,2] and q = [1,null,2], one row per call of isSameTree:
| Step | Call | if not p or not q | Returns |
|---|---|---|---|
| 1 | isSameTree(1, 1), the two roots | False: both nodes exist | waits for its two child pairs |
| 2 | isSameTree(2, None), the left children | True: q is missing | p is None and q is None = False |
| 3 | isSameTree(None, 2), the right children | True: p is missing | p is None and q is None = False |
| 4 | back at isSameTree(1, 1) | 1 == 1 and False and False = False | |
| End | False |
At step 2, return True would end the walk with a match. The roots are equal and both child pairs would pass, so [1,2] and [1,null,2] would be reported as the same tree.
p = [1,2,3], q = [1,2,3]trueExample 2, p = [1,2] and q = [1,null,2], one row per call of isSameTree:
| Step | Call | if not p or not q | Returns |
|---|---|---|---|
| 1 | isSameTree(1, 1), the two roots | False: both nodes exist | waits for its two child pairs |
| 2 | isSameTree(2, None), the left children | True: q is missing | p is None and q is None = False |
| 3 | isSameTree(None, 2), the right children | True: p is missing | p is None and q is None = False |
| 4 | back at isSameTree(1, 1) | 1 == 1 and False and False = False | |
| End | False |
At step 2, return True would end the walk with a match. The roots are equal and both child pairs would pass, so [1,2] and [1,null,2] would be reported as the same tree.
| 1 | Two trees match only if they match position by position, so `isSameTree(p, q)` takes one node from each tree and pairs the children by position: `p.left` with `q.left`, and `p.right` with `q.right`. |
| 2 | A pair of present nodes matches when `p.val == q.val` and both child pairs match. Nothing deeper than the two child pairs is read. |
| 3 | The shape: `if not p or not q: return p is None and q is None`; `left_same = isSameTree(p.left, q.left)`; `right_same = isSameTree(p.right, q.right)`; `return p.val == q.val and left_same and right_same`. |
| 4 | The trap: a pair with one missing node must return `False`. With `return True` there, `[1,2]` and `[1,null,2]` look like the same tree. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Bottom-Up DFS walks one tree and lets every subtree hand its parent one finished answer. Some problems give you two trees. To compare them, one call has to hold one node from each tree. Two Tree Walk keeps the two nodes at the same position: isSameTree(p, q) takes a node of each tree, pairs the children by position, and builds its answer from the two values and the answers for the two child pairs. Nothing deeper than the two child pairs is read, and neither tree is ever walked alone.
🏢 The Analogy: Two Clerks With Two Org Charts
Two clerks each hold an org chart and compare them box by box. They start at the two top boxes. If the names differ, the charts differ. If both boxes exist and match, they step down together: the left report of one chart with the left report of the other, then the right with the right. If one clerk finds a box and the other finds an empty space, the charts differ at that position, before any name is read.
🔑 Why It Works
isSameTree(p, q) is True exactly when p.val == q.val and the left pair and the right pair both match, so a difference anywhere makes the answer False at the top. Each position is visited once. The trap sits in the base case: a pair with exactly one missing node must give False, so the line is return p is None and q is None, not return True.
Returning
Truewhen only one of the two nodes is missingReading
p.valbefore checking that both nodes existComparing child nodes with
==instead of walking themComparing the two lists of values instead of walking the trees together
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The roots of two binary trees" and a question about whether they have "the same shape" and "the same value" at every position: the answer for a pair of nodes depends on the pair and on the pairs below it. That is the signal for Two Tree Walk: one call takes a node from each tree.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
isSameTree(p, q) is True exactly when p.val == q.val, left_same and right_same, where left_same = isSameTree(p.left, q.left) and right_same = isSameTree(p.right, q.right). A pair with a missing node is True only when both nodes are missing: return p is None and q is None.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: a pair with one missing node returns
p is None and q is None, neverTrue. On[1,2]and[1,null,2]the pair(2, None)must giveFalse.Check for a missing node before reading
p.valorq.val. On[1,2]and[1], readingq.valfirst crashes with anAttributeErrorat the pair(2, None).Compare values, not nodes:
p.left == q.leftcompares node objects, and two separate trees never share nodes, so[1,2,3]and[1,2,3]returnFalse.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Two Tree Walk. The question is about two trees, so one call has to hold one node from each tree. I write isSameTree of p and q, and I pair the children by position: p dot left with q dot left, and p dot right with q dot right. The base case is the key. If a node is missing on either side, the trees match at this position only when both are missing, so I return p is None and q is None. Returning True there would hide a shape difference. Otherwise the pair matches when the two values are equal and both child pairs match. Each position is visited once, so the time is the size of the smaller tree, and the recursion stack is as deep as the shallower tree. The trap I avoid is treating one missing node as a match.
Complexity & Mathematical Proof
O(min(N, M))
Look at the code: isSameTree is called on the two roots, and again on a pair of children only when both nodes of the pair exist. A pair of present nodes sits at a position that exists in both trees, so there are at most min(N, M) of them. Each present pair makes two calls on its children, so there are at most 2 * min(N, M) + 1 calls in all. Each call does O(1) work: one test, two assignments and one comparison. Total: O(min(N, M)).
O(H) recursion stack
The recursion goes down one level per call, and it only goes down while both nodes exist, so the stack holds at most H + 1 frames, where H is the height of the shallower tree. Each frame keeps p, q, left_same and right_same. The answer is one boolean. Nothing else grows with the trees.
Derivation Progression
One call for the two roots, and two calls for every pair of present nodes. A pair with a missing node makes no further calls.
O(1)
Test if not p or not q, store left_same and right_same, compare p.val with q.val.
The calls times the work per call. Both child calls run before the comparison, so a difference near the root does not shorten the walk.
Variable Definitions
Number of nodes in p
Number of nodes in q
Height of the shallower of the two trees: the walk never goes deeper
Memory Architecture & Bounds
O(H): one frame per level of the current pair's path
O(1): each frame keeps four names, no extra structure
O(1): one boolean
Boundary Best / Worst Cases
time when either tree is empty: the first call ends in the base case
time; the stack depth is the height of the shallower tree
time and an stack, even when the trees differ at the root, because both child calls run before the comparison
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the same shape", "the same value at every position", two roots p and q. A question about two trees at once: Two Tree Walk, where one call holds a node from each tree and pairs the children by position.
nodes and values in . Writing both trees as lists first costs extra memory; the pair walk needs only an recursion stack and does work.
A chain of 100 nodes is only 100 calls deep, but the same walk on a chain of nodes is past CPython's default recursion limit of 1000: use an explicit stack of pairs. Comparing two trees by writing both as text is correct only if every missing child is written too (null); without the markers, different shapes can give the same text.
Same Tree (LeetCode 100)
Two binary trees are given by their root nodes, p and q. Either tree may be empty. The trees are the same when they have the same shape and, at every position, the two nodes hold the same value.
Same shape means that wherever one tree has a left child, the other tree has a left child too, and the same for right children. Return True when the trees are the same and False otherwise.
Worked Examples
p = [1,2,3], q = [1,2,3]truep = [1,2], q = [1,null,2]falsep and the right child in q. The shapes differ.p = [1,2,1], q = [1,1,2]false⚖️Formal Constraints & Bounds
The number of nodes in both trees is in the range
[0, 100].-104 <= Node.val <= 104
Core Insight
Walk both trees at once and pair the children by position. A pair with one missing node means the shapes differ, so the answer is False. A pair of present nodes is the same when the values are equal and both child pairs are the same.
Real-World Scenario & Production Applications
A tool that compares two parsed documents, or two syntax trees of a program, walks both trees together and stops at the first position where they differ. A test that checks an expected nested document against an actual one does the same: it pairs the entries at each position and reports where the two disagree.
Step-by-Step Execution Trace Table
Example 2, p = [1,2] and q = [1,null,2], one row per call of isSameTree:
| Step | Call | if not p or not q | Returns |
|---|---|---|---|
| 1 | isSameTree(1, 1), the two roots | False: both nodes exist | waits for its two child pairs |
| 2 | isSameTree(2, None), the left children | True: q is missing | p is None and q is None = False |
| 3 | isSameTree(None, 2), the right children | True: p is missing | p is None and q is None = False |
| 4 | back at isSameTree(1, 1) | 1 == 1 and False and False = False | |
| End | False |
At step 2, return True would end the walk with a match. The roots are equal and both child pairs would pass, so [1,2] and [1,null,2] would be reported as the same tree.
p = [1,2,3], q = [1,2,3]trueExample 2, p = [1,2] and q = [1,null,2], one row per call of isSameTree:
| Step | Call | if not p or not q | Returns |
|---|---|---|---|
| 1 | isSameTree(1, 1), the two roots | False: both nodes exist | waits for its two child pairs |
| 2 | isSameTree(2, None), the left children | True: q is missing | p is None and q is None = False |
| 3 | isSameTree(None, 2), the right children | True: p is missing | p is None and q is None = False |
| 4 | back at isSameTree(1, 1) | 1 == 1 and False and False = False | |
| End | False |
At step 2, return True would end the walk with a match. The roots are equal and both child pairs would pass, so [1,2] and [1,null,2] would be reported as the same tree.
| 1 | Two trees match only if they match position by position, so `isSameTree(p, q)` takes one node from each tree and pairs the children by position: `p.left` with `q.left`, and `p.right` with `q.right`. |
| 2 | A pair of present nodes matches when `p.val == q.val` and both child pairs match. Nothing deeper than the two child pairs is read. |
| 3 | The shape: `if not p or not q: return p is None and q is None`; `left_same = isSameTree(p.left, q.left)`; `right_same = isSameTree(p.right, q.right)`; `return p.val == q.val and left_same and right_same`. |
| 4 | The trap: a pair with one missing node must return `False`. With `return True` there, `[1,2]` and `[1,null,2]` look like the same tree. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Bottom-Up DFS walks one tree and lets every subtree hand its parent one finished answer. Some problems give you two trees. To compare them, one call has to hold one node from each tree. Two Tree Walk keeps the two nodes at the same position: isSameTree(p, q) takes a node of each tree, pairs the children by position, and builds its answer from the two values and the answers for the two child pairs. Nothing deeper than the two child pairs is read, and neither tree is ever walked alone.
🏢 The Analogy: Two Clerks With Two Org Charts
Two clerks each hold an org chart and compare them box by box. They start at the two top boxes. If the names differ, the charts differ. If both boxes exist and match, they step down together: the left report of one chart with the left report of the other, then the right with the right. If one clerk finds a box and the other finds an empty space, the charts differ at that position, before any name is read.
🔑 Why It Works
isSameTree(p, q) is True exactly when p.val == q.val and the left pair and the right pair both match, so a difference anywhere makes the answer False at the top. Each position is visited once. The trap sits in the base case: a pair with exactly one missing node must give False, so the line is return p is None and q is None, not return True.
Returning
Truewhen only one of the two nodes is missingReading
p.valbefore checking that both nodes existComparing child nodes with
==instead of walking themComparing the two lists of values instead of walking the trees together
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
"The roots of two binary trees" and a question about whether they have "the same shape" and "the same value" at every position: the answer for a pair of nodes depends on the pair and on the pairs below it. That is the signal for Two Tree Walk: one call takes a node from each tree.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
isSameTree(p, q) is True exactly when p.val == q.val, left_same and right_same, where left_same = isSameTree(p.left, q.left) and right_same = isSameTree(p.right, q.right). A pair with a missing node is True only when both nodes are missing: return p is None and q is None.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
The card's trap: a pair with one missing node returns
p is None and q is None, neverTrue. On[1,2]and[1,null,2]the pair(2, None)must giveFalse.Check for a missing node before reading
p.valorq.val. On[1,2]and[1], readingq.valfirst crashes with anAttributeErrorat the pair(2, None).Compare values, not nodes:
p.left == q.leftcompares node objects, and two separate trees never share nodes, so[1,2,3]and[1,2,3]returnFalse.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Two Tree Walk. The question is about two trees, so one call has to hold one node from each tree. I write isSameTree of p and q, and I pair the children by position: p dot left with q dot left, and p dot right with q dot right. The base case is the key. If a node is missing on either side, the trees match at this position only when both are missing, so I return p is None and q is None. Returning True there would hide a shape difference. Otherwise the pair matches when the two values are equal and both child pairs match. Each position is visited once, so the time is the size of the smaller tree, and the recursion stack is as deep as the shallower tree. The trap I avoid is treating one missing node as a match.
Complexity & Mathematical Proof
O(min(N, M))
Look at the code: isSameTree is called on the two roots, and again on a pair of children only when both nodes of the pair exist. A pair of present nodes sits at a position that exists in both trees, so there are at most min(N, M) of them. Each present pair makes two calls on its children, so there are at most 2 * min(N, M) + 1 calls in all. Each call does O(1) work: one test, two assignments and one comparison. Total: O(min(N, M)).
O(H) recursion stack
The recursion goes down one level per call, and it only goes down while both nodes exist, so the stack holds at most H + 1 frames, where H is the height of the shallower tree. Each frame keeps p, q, left_same and right_same. The answer is one boolean. Nothing else grows with the trees.
Derivation Progression
One call for the two roots, and two calls for every pair of present nodes. A pair with a missing node makes no further calls.
O(1)
Test if not p or not q, store left_same and right_same, compare p.val with q.val.
The calls times the work per call. Both child calls run before the comparison, so a difference near the root does not shorten the walk.
Variable Definitions
Number of nodes in p
Number of nodes in q
Height of the shallower of the two trees: the walk never goes deeper
Memory Architecture & Bounds
O(H): one frame per level of the current pair's path
O(1): each frame keeps four names, no extra structure
O(1): one boolean
Boundary Best / Worst Cases
time when either tree is empty: the first call ends in the base case
time; the stack depth is the height of the shallower tree
time and an stack, even when the trees differ at the root, because both child calls run before the comparison
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Triggers: "the same shape", "the same value at every position", two roots p and q. A question about two trees at once: Two Tree Walk, where one call holds a node from each tree and pairs the children by position.
nodes and values in . Writing both trees as lists first costs extra memory; the pair walk needs only an recursion stack and does work.
A chain of 100 nodes is only 100 calls deep, but the same walk on a chain of nodes is past CPython's default recursion limit of 1000: use an explicit stack of pairs. Comparing two trees by writing both as text is correct only if every missing child is written too (null); without the markers, different shapes can give the same text.