DSA-080 · FOCUSED PRACTICE
Symmetric Tree
Core · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 23500 deterministic checks. Learner drafts are not executed.
Understand the problem
Return whether a binary tree is symmetric: its left subtree is the value-preserving mirror of its right subtree.
- Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
- Preserve every original value, node identity, and left/right edge. Compact level-order arrays in examples are adapters, consuming two child slots per nonnull queued parent; they are not heap-indexed arrays.
- Empty and single-node trees are symmetric. Duplicate values are allowed and are not unique identities. Mirror comparison pairs left/ right and right/left child positions, not the ordinary same-side pairs used for Same Tree.
Examples
Input:
[1,2,2,3,4,4,3]
Output:trueOpposite positions match through both levels.
Input:
[1,2,2,null,3,null,3]
Output:falseBoth 3s lie on right edges of their parents; their null positions do not mirror.
Before you start
- Ordered tree equality and null positions
- Stacks of mirrored subtree pairs
Recognize the structure
The mirror relation flips each subsequent L/R decision. Start with the root’s two children, compare their values/nullness, then pair outer children and inner children.
Your Java attempt
Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.
Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.
No unsaved text changes · 148/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Which child of the right subtree mirrors the left child of the left subtree?
Hint 2
A missing position has to mirror another missing position.
Hint 3
Start with the root children and repeatedly compare crossed child pairs.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Recursive mirror relation
mirror(a,b) accepts two nulls; rejects one null or unequal values; otherwise requires mirror(a.left,b.right) and mirror(a.right,b.left). In [1,2,2,null,3,null,3], equal 2s cannot rescue the outer pair null versus 3. The explicit implementation is the same relation with depth-safe frames.
Improve the baseline
Seed across the axis
For nonempty root push (root.left,root.right). The root matches itself and requires no separate value comparison.
Separate null agreement from value agreement
Two absent mirrored positions are satisfied. One absent position or different values proves asymmetry.
Cross the child directions
Push a.right/b.left and a.left/b.right. The second pair is visited first, producing an explicit deterministic outer-first traversal.
Why it is correct
Mirror-pair invariant
A pair always denotes positions whose complete root paths complement each other after the root.
Preserve by crossing
Matching nonnull values need mirrored outer and inner descendants. Crossed child pairs enumerate exactly these required positions.
Termination and decision
Every relevant pair is eventually discharged in a finite proper tree. A mismatch is a witness; exhausting all pairs proves symmetry including null structure.
Complete Java reference and baseline
Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.
import java.util.*;
public final class Solution {
public static final class Node {
public final int value;
public Node left, right;
public Node(int value) { this.value = value; }
}
private record Pair(Node a, Node b) {}
public static boolean symmetric(Node root) {
if (root == null) return true;
ArrayDeque<Pair> pending = new ArrayDeque<>();
pending.push(new Pair(root.left,root.right));
while (!pending.isEmpty()) {
Pair pair = pending.pop();
if (pair.a == null || pair.b == null) {
if (pair.a != pair.b) return false;
continue;
}
if (pair.a.value != pair.b.value) return false;
pending.push(new Pair(pair.a.right,pair.b.left));
pending.push(new Pair(pair.a.left,pair.b.right));
}
return true;
}
private static boolean mirror(Node a, Node b) {
if (a == null || b == null) return a == b;
return a.value == b.value && mirror(a.left,b.right) && mirror(a.right,b.left);
}
public static boolean baseline(Node root) { return root == null || mirror(root.left,root.right); }
}
Read the meaningful blocks
Reuse the Pair wrapper idea
Pair fields can be null while the deque item stays nonnull.
Avoid equal-level value shortcuts
A palindromic list of nonnull values at each level can hide missing positions.
Keep the tree read-only
No inversion is needed to compare mirrors, so there is no restoration or aliasing obligation from mutation.
Complexity
Worst-case O(n) time and O(h) explicit DFS pair space. A single-node tree creates one both-null pair; short-circuiting may visit much less than the whole tree.
The recursive baseline has O(n) time and O(h) calls but can overflow on deep mirrored chains. Mirroring a copy before Same Tree requires O(n) additional node allocation.
Exact-state walkthroughs
Reveal normal and boundary traces
Outer and inner mirror pairs
Input: [1,2,2,3,4,4,3] · Result: true
Step 1 of 9: Create nullable comparison pairs.
A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.
Phase: initial.
Original objects — unchanged source edges
- T0: 1left → T1right → T2
- T1: 2left → T3right → T4
- T2: 2left → T5right → T6
- T3: 3left → nullright → null
- T4: 4left → nullright → null
- T5: 4left → nullright → null
- T6: 3left → nullright → null
Current pair: null ↔ null. Children are paired left/right and right/left.
Nullable pairs — stack top at right
- T1 ↔ T2
Null positions participate in comparison. Equal values do not replace shape checks; a rejected pair leaves later work unprocessed.
Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.
| Variable | Value |
|---|---|
| treeNodes | [{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}] |
| pending | [{"a":"T1","b":"T2"}] |
| checked | [] |
| mode | "mirror positions" |
| phase | "initial" |
| pair | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static final class Node { 4 public final int value; 5 public Node left, right; 6 public Node(int value) { this.value = value; } 7 } 8 private record Pair(Node a, Node b) {} 9 public static boolean symmetric(Node root) { 10 if (root == null) return true; 11 ArrayDeque<Pair> pending = new ArrayDeque<>(); 12 pending.push(new Pair(root.left,root.right)); 13 while (!pending.isEmpty()) { 14 Pair pair = pending.pop(); 15 if (pair.a == null || pair.b == null) { 16 if (pair.a != pair.b) return false; 17 continue; 18 } 19 if (pair.a.value != pair.b.value) return false; 20 pending.push(new Pair(pair.a.right,pair.b.left)); 21 pending.push(new Pair(pair.a.left,pair.b.right)); 22 } 23 return true; 24 } 25 private static boolean mirror(Node a, Node b) { 26 if (a == null || b == null) return a == b; 27 return a.value == b.value && mirror(a.left,b.right) && mirror(a.right,b.left); 28 } 29 public static boolean baseline(Node root) { return root == null || mirror(root.left,root.right); } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create nullable comparison pairs.
A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}]- pending
[{"a":"T1","b":"T2"}]- checked
[]- mode
"mirror positions"- phase
"initial"- pair
null
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}]- pending
[{"a":"T4","b":"T5"},{"a":"T3","b":"T6"}]- checked
[{"a":"T1","b":"T2","matches":true}]- mode
"mirror positions"- phase
"match"- pair
{"a":"T1","b":"T2"}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}]- pending
[{"a":"T4","b":"T5"},{"a":null,"b":null},{"a":null,"b":null}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T6","matches":true}]- mode
"mirror positions"- phase
"match"- pair
{"a":"T3","b":"T6"}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}]- pending
[{"a":"T4","b":"T5"},{"a":null,"b":null}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T6","matches":true},{"a":null,"b":null,"matches":true}]- mode
"mirror positions"- phase
"both-null"- pair
{"a":null,"b":null}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}]- pending
[{"a":"T4","b":"T5"}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T6","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true}]- mode
"mirror positions"- phase
"both-null"- pair
{"a":null,"b":null}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}]- pending
[{"a":null,"b":null},{"a":null,"b":null}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T6","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true},{"a":"T4","b":"T5","matches":true}]- mode
"mirror positions"- phase
"match"- pair
{"a":"T4","b":"T5"}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}]- pending
[{"a":null,"b":null}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T6","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true},{"a":"T4","b":"T5","matches":true},{"a":null,"b":null,"matches":true}]- mode
"mirror positions"- phase
"both-null"- pair
{"a":null,"b":null}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":"T3","right":"T4"},{"id":"T2","value":2,"left":"T5","right":"T6"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":4,"left":null,"right":null},{"id":"T5","value":4,"left":null,"right":null},{"id":"T6","value":3,"left":null,"right":null}]- pending
[]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T6","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true},{"a":"T4","b":"T5","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true}]- mode
"mirror positions"- phase
"both-null"- pair
{"a":null,"b":null}
- Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
- result
true
Equal values with nonmirrored null positions
Input: [1,2,2,null,3,null,3] · Result: false
Step 1 of 4: Create nullable comparison pairs.
A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.
Phase: initial.
Original objects — unchanged source edges
- T0: 1left → T1right → T2
- T1: 2left → nullright → T3
- T2: 2left → nullright → T4
- T3: 3left → nullright → null
- T4: 3left → nullright → null
Current pair: null ↔ null. Children are paired left/right and right/left.
Nullable pairs — stack top at right
- T1 ↔ T2
Null positions participate in comparison. Equal values do not replace shape checks; a rejected pair leaves later work unprocessed.
Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.
| Variable | Value |
|---|---|
| treeNodes | [{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":2,"left":null,"right":"T4"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null}] |
| pending | [{"a":"T1","b":"T2"}] |
| checked | [] |
| mode | "mirror positions" |
| phase | "initial" |
| pair | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static final class Node { 4 public final int value; 5 public Node left, right; 6 public Node(int value) { this.value = value; } 7 } 8 private record Pair(Node a, Node b) {} 9 public static boolean symmetric(Node root) { 10 if (root == null) return true; 11 ArrayDeque<Pair> pending = new ArrayDeque<>(); 12 pending.push(new Pair(root.left,root.right)); 13 while (!pending.isEmpty()) { 14 Pair pair = pending.pop(); 15 if (pair.a == null || pair.b == null) { 16 if (pair.a != pair.b) return false; 17 continue; 18 } 19 if (pair.a.value != pair.b.value) return false; 20 pending.push(new Pair(pair.a.right,pair.b.left)); 21 pending.push(new Pair(pair.a.left,pair.b.right)); 22 } 23 return true; 24 } 25 private static boolean mirror(Node a, Node b) { 26 if (a == null || b == null) return a == b; 27 return a.value == b.value && mirror(a.left,b.right) && mirror(a.right,b.left); 28 } 29 public static boolean baseline(Node root) { return root == null || mirror(root.left,root.right); } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create nullable comparison pairs.
A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":2,"left":null,"right":"T4"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null}]- pending
[{"a":"T1","b":"T2"}]- checked
[]- mode
"mirror positions"- phase
"initial"- pair
null
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":2,"left":null,"right":"T4"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null}]- pending
[{"a":"T3","b":null},{"a":null,"b":"T4"}]- checked
[{"a":"T1","b":"T2","matches":true}]- mode
"mirror positions"- phase
"match"- pair
{"a":"T1","b":"T2"}
- Reject an exact null-position or value mismatch.
This corresponding position is a complete counterexample; remaining pending comparisons need not run.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":2,"left":null,"right":"T3"},{"id":"T2","value":2,"left":null,"right":"T4"},{"id":"T3","value":3,"left":null,"right":null},{"id":"T4","value":3,"left":null,"right":null}]- pending
[{"a":"T3","b":null}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":null,"b":"T4","matches":false}]- mode
"mirror positions"- phase
"reject"- pair
{"a":null,"b":"T4"}
- Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
- result
false
Empty tree
Input: [] · Result: true
Step 1 of 2: Create nullable comparison pairs.
A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.
Phase: initial.
Original objects — unchanged source edges
Empty tree.
Current pair: null ↔ null. Children are paired left/right and right/left.
Nullable pairs — stack top at right
Empty.
Null positions participate in comparison. Equal values do not replace shape checks; a rejected pair leaves later work unprocessed.
Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.
| Variable | Value |
|---|---|
| treeNodes | [] |
| pending | [] |
| checked | [] |
| mode | "mirror positions" |
| phase | "initial" |
| pair | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static final class Node { 4 public final int value; 5 public Node left, right; 6 public Node(int value) { this.value = value; } 7 } 8 private record Pair(Node a, Node b) {} 9 public static boolean symmetric(Node root) { 10 if (root == null) return true; 11 ArrayDeque<Pair> pending = new ArrayDeque<>(); 12 pending.push(new Pair(root.left,root.right)); 13 while (!pending.isEmpty()) { 14 Pair pair = pending.pop(); 15 if (pair.a == null || pair.b == null) { 16 if (pair.a != pair.b) return false; 17 continue; 18 } 19 if (pair.a.value != pair.b.value) return false; 20 pending.push(new Pair(pair.a.right,pair.b.left)); 21 pending.push(new Pair(pair.a.left,pair.b.right)); 22 } 23 return true; 24 } 25 private static boolean mirror(Node a, Node b) { 26 if (a == null || b == null) return a == b; 27 return a.value == b.value && mirror(a.left,b.right) && mirror(a.right,b.left); 28 } 29 public static boolean baseline(Node root) { return root == null || mirror(root.left,root.right); } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create nullable comparison pairs.
A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.
- treeNodes
[]- pending
[]- checked
[]- mode
"mirror positions"- phase
"initial"- pair
null
- Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
- result
true
Deep positions can mirror despite repeated values
Input: [1,1,1,1,null,null,1] · Result: true
Step 1 of 7: Create nullable comparison pairs.
A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.
Phase: initial.
Original objects — unchanged source edges
- T0: 1left → T1right → T2
- T1: 1left → T3right → null
- T2: 1left → nullright → T4
- T3: 1left → nullright → null
- T4: 1left → nullright → null
Current pair: null ↔ null. Children are paired left/right and right/left.
Nullable pairs — stack top at right
- T1 ↔ T2
Null positions participate in comparison. Equal values do not replace shape checks; a rejected pair leaves later work unprocessed.
Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.
| Variable | Value |
|---|---|
| treeNodes | [{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":"T3","right":null},{"id":"T2","value":1,"left":null,"right":"T4"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":1,"left":null,"right":null}] |
| pending | [{"a":"T1","b":"T2"}] |
| checked | [] |
| mode | "mirror positions" |
| phase | "initial" |
| pair | null |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 public static final class Node { 4 public final int value; 5 public Node left, right; 6 public Node(int value) { this.value = value; } 7 } 8 private record Pair(Node a, Node b) {} 9 public static boolean symmetric(Node root) { 10 if (root == null) return true; 11 ArrayDeque<Pair> pending = new ArrayDeque<>(); 12 pending.push(new Pair(root.left,root.right)); 13 while (!pending.isEmpty()) { 14 Pair pair = pending.pop(); 15 if (pair.a == null || pair.b == null) { 16 if (pair.a != pair.b) return false; 17 continue; 18 } 19 if (pair.a.value != pair.b.value) return false; 20 pending.push(new Pair(pair.a.right,pair.b.left)); 21 pending.push(new Pair(pair.a.left,pair.b.right)); 22 } 23 return true; 24 } 25 private static boolean mirror(Node a, Node b) { 26 if (a == null || b == null) return a == b; 27 return a.value == b.value && mirror(a.left,b.right) && mirror(a.right,b.left); 28 } 29 public static boolean baseline(Node root) { return root == null || mirror(root.left,root.right); } 30 } 31
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Create nullable comparison pairs.
A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":"T3","right":null},{"id":"T2","value":1,"left":null,"right":"T4"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":1,"left":null,"right":null}]- pending
[{"a":"T1","b":"T2"}]- checked
[]- mode
"mirror positions"- phase
"initial"- pair
null
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":"T3","right":null},{"id":"T2","value":1,"left":null,"right":"T4"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":1,"left":null,"right":null}]- pending
[{"a":null,"b":null},{"a":"T3","b":"T4"}]- checked
[{"a":"T1","b":"T2","matches":true}]- mode
"mirror positions"- phase
"match"- pair
{"a":"T1","b":"T2"}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":"T3","right":null},{"id":"T2","value":1,"left":null,"right":"T4"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":1,"left":null,"right":null}]- pending
[{"a":null,"b":null},{"a":null,"b":null},{"a":null,"b":null}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T4","matches":true}]- mode
"mirror positions"- phase
"match"- pair
{"a":"T3","b":"T4"}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":"T3","right":null},{"id":"T2","value":1,"left":null,"right":"T4"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":1,"left":null,"right":null}]- pending
[{"a":null,"b":null},{"a":null,"b":null}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T4","matches":true},{"a":null,"b":null,"matches":true}]- mode
"mirror positions"- phase
"both-null"- pair
{"a":null,"b":null}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":"T3","right":null},{"id":"T2","value":1,"left":null,"right":"T4"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":1,"left":null,"right":null}]- pending
[{"a":null,"b":null}]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T4","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true}]- mode
"mirror positions"- phase
"both-null"- pair
{"a":null,"b":null}
- Discharge this pair and expand only matching nonnull positions.
Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":"T3","right":null},{"id":"T2","value":1,"left":null,"right":"T4"},{"id":"T3","value":1,"left":null,"right":null},{"id":"T4","value":1,"left":null,"right":null}]- pending
[]- checked
[{"a":"T1","b":"T2","matches":true},{"a":"T3","b":"T4","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true}]- mode
"mirror positions"- phase
"both-null"- pair
{"a":null,"b":null}
- Return the problem-specific identity, value, optional result, or round-trip observation.
Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.
- result
true
Test the contract
Input:
null
Output:trueNo unmatched positions.
Input:
[1]
Output:trueBoth children absent.
Input:
[1,2,2,null,3,null,3]
Output:falseNull-side mismatch.
Input:
Two mirrored chains of 49,999 nodes under one root
Output:trueDeep symmetry without Java recursion.
Common mistakes and counterexamples
Compare a.left with b.left
Counterexample: Symmetric subtrees need opposite edge directions.
Cross the comparisons at every level.
Check only level values without null positions
Counterexample: The two right-side 3s in [1,2,2,null,3,null,3] look like [3,3].
Include nullness at corresponding mirrored positions.
Invert the original left subtree to compare
Counterexample: A read-only query would silently mutate its caller’s tree.
Compare mirrored pairs directly.
Follow-ups
Return the asymmetric positions.
Record paired paths and the first mismatch. Include both null/value details; define outer-first or inner-first order.
Count mirrored node pairs.
Count only nonnull matching pairs and decide whether the root contributes one. A boolean early exit may no longer be enough if reporting all mismatches.
Use breadth-first mirror comparison.
The same Pair relation works in a queue; auxiliary storage changes to O(w), and first mismatch follows breadth-first rather than depth-first order.
Related foundations
- Tree foundations: structure, depth, and traversal state
- DFS: traverse components with explicit state meaning