Same Tree
Mahabharata — The Twin Formations — Are Two Battle Arrays Identical?
दो वृक्ष — एक जैसे?। रचना और मूल्य — दोनों में एकसमान हों॥
*Two trees — the same? Structure and values — must be identical in both.*
The Story
Check if two binary trees are structurally identical with the same node values.
For `p=[1,2,3]`, `q=[1,2,3]`: true. For `p=[1,2]`, `q=[1,null,2]`: false (different structure). For `p=[1,2,1]`, `q=[1,1,2]`: false (different values).
**Recursive:** ```java public boolean isSameTree(TreeNode p, TreeNode q) { if (p == null && q == null) return true; // Both empty if (p == null || q == null) return false; // One empty return p.val == q.val && isSameTree(p.left, q.left) // Left subtrees same && isSameTree(p.right, q.right); // Right subtrees same } ```
This is the simplest and most elegant tree problem.
Trace `p=[1,2,3]`, `q=[1,2,3]`: - same(1,1): 1==1 && same(2,2) && same(3,3) - same(2,2): 2==2 && same(null,null) && same(null,null) → true - same(3,3): same → true - Result: true ✓
Trace `p=[1,2]`, `q=[1,null,2]`: - same(p=1,q=1): 1==1 && same(p.left=2, q.left=null) - same(2, null): p not null, q null → false ✓
**Three base cases:** Both null → true; one null → false; values different → false.
The Serialize-and-Compare Approach
Serialize both trees to strings (with null markers), compare strings. O(n).
// Recursive IS optimal. Serialize approach:
String serialize(TreeNode root) {
if (root == null) return "null,";
return root.val + "," + serialize(root.left) + serialize(root.right);
}
// Two trees same iff serialize(p).equals(serialize(q))The Three-Case Recursive Comparison
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true;
if (p == null || q == null) return false;
return p.val == q.val
&& isSameTree(p.left, q.left)
&& isSameTree(p.right, q.right);
}Step-by-Step Walkthrough
p=[], q=[]: both null → true ✅ p=[1], q=[1]: 1==1 && same(null,null) && same(null,null) → true ✅
Deep Insight
**isSameTree vs isSymmetric (mirror):** - isSameTree(p, q): p.left with q.left, p.right with q.right (parallel comparison) - mirror(left, right): left.left with right.right, left.right with right.left (cross comparison)
The structural difference between these two functions is subtle but important.
**tr-10 (Subtree) uses isSameTree:** Checking every node of the main tree as a potential subtree root, calling isSameTree at each match.
**Short-circuit evaluation:** Java's `&&` stops early. If p.val != q.val, the recursive calls for left and right are never made — efficient pruning.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n) | O(h) | O(h) call stack |
| Optimal | O(n) | O(h) | Visit each node pair once |
Pattern Recognition
✅ Same tree: three-case recursive comparison ✅ Cross-compare (p.left,q.left) and (p.right,q.right) ✅ Used as helper in tr-10 (Subtree check) ✅ vs mirror(): cross vs parallel comparison **LeetCode Trigger Phrases:** → "same tree" → Two trees structurally identical → Helper function for subtree problems
Bhagavad Gita 5.18
विद्याविनयसम्पन्ने ब्राह्मणे गवि हस्तिनि। शुनि चैव श्वपाके च पण्डिताः समदर्शिनः॥
The wise see with equal vision a learned brahmin, a cow, an elephant, a dog, and an outcaste.
Connection: The Same Tree problem asks: are these two trees exactly alike, in every node and at every level? Like the sage's equal vision that sees the same divine essence in all apparently different beings, the isSameTree function looks beyond surface differences and checks for true structural and value identity. The recursive descent verifies this at every node — are these two beings (nodes) truly the same in essence (value) and in their relationships (children)?