#100 Same Tree
frequently reported atBloombergAmazonGoogleMicrosoftMetaLinkedIn
the problem
In plain words
Return true if two binary trees have the same shape and the same values in the same places.
in p = [1,2,3], q = [1,2,3]
out true
in p = [1,2], q = [1,null,2]
out false
Same values, different shape.
in p = [1,2,1], q = [1,1,2]
out false
- 0 ≤ number of nodes in each tree ≤ 100
- -10⁴ ≤ Node.val ≤ 10⁴
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTree DFS (bottom-up)
Two trees are equal if their roots match, their left subtrees are equal and their right subtrees are equal. Handle the null cases first.
solutions
From brute force to optimal
Write each tree as a preorder string with a marker for null, then compare.
- Preorder with "#" for null and "," after every value.
- Compare the two strings.
Each tree is written once, then one string comparison.
Both strings are stored.
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { return serialize(p).equals(serialize(q)); } // preorder with a "#" for every missing child makes the string unique per tree private String serialize(TreeNode node) { StringBuilder sb = new StringBuilder(); write(node, sb); return sb.toString(); } private void write(TreeNode node, StringBuilder sb) { if (node == null) { sb.append("#,"); return; } sb.append(node.val).append(','); write(node.left, sb); write(node.right, sb); }}Compare the two roots, then recurse on (left, left) and (right, right).
- Both null → true.
- One null → false.
- Values differ → false.
- Return same(left) && same(right).
Stops at the first difference; at most every node of the smaller tree.
Recursion goes only as deep as both trees go together.
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; // both empty: same if (p == null || q == null) return false; // exactly one empty: different shape if (p.val != q.val) return false; // different value return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }}Same checks as the recursion, but pairs of nodes wait in a queue.
- Offer (p, q).
- Poll a pair; apply the three checks.
- Offer (left, left) and (right, right).
Each pair is checked once.
Queue of pairs — at most about one level wide.
class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { Deque<TreeNode[]> pairs = new ArrayDeque<>(); // the pair array may hold nulls; the deque never does pairs.offer(new TreeNode[] {p, q}); while (!pairs.isEmpty()) { TreeNode[] pair = pairs.poll(); TreeNode a = pair[0], b = pair[1]; if (a == null && b == null) continue; if (a == null || b == null || a.val != b.val) return false; pairs.offer(new TreeNode[] {a.left, b.left}); pairs.offer(new TreeNode[] {a.right, b.right}); } return true; }}in the room
How to say it in the interview
talk track
- Say the three checks in order: both null, one null, values differ — then recurse on both pairs with
&&so it stops early.
traps
- Serializing without separators: trees [12,3] and [1,23] would both become "123".
- Serializing without null markers: different shapes produce the same string.
what they ask next
Follow-ups
Subtree of Another Tree (LC 572)?
Run Same Tree from every node of the big tree: O(n·m). For O(n + m), serialize both with null markers and a separator on both sides of every value (so ",2," can't match inside ",12,") and use KMP string matching (or hash every subtree).
Symmetric Tree (LC 101)?
The same lockstep recursion on one tree's two halves, crossing the pairs: (a.left, b.right) and (a.right, b.left).
before you submit
Edge cases to test
- Both empty → true; only one empty → false.
- Same values, different shape: [1,2] vs [1,null,2] → false.
- Values that blur together (12, 3 vs 1, 23) only matter if you compare strings — use separators.
practise next
Similar problems
- #101Symmetric TreeEasyin Tree Recursion
- #572Subtree of Another TreeEasyin Tree Recursion
- #226Invert Binary TreeEasyin Tree Recursion
- #297Serialize and Deserialize Binary TreeHardin Traversals