DSA-086 · Verify identity membership, then intersect ancestor paths
Lowest Common Ancestor of a Binary Tree
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 62143 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the lowest common ancestor of two requested node objects in a binary tree. Return null if either requested object is absent or null.
- 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.
- p and q are object references, not values. They may be identical, may be external objects with values matching the tree, or may be null. A present node is its own ancestor; p==q returns that object only if it belongs to the tree. Return an original node identity, never a copied node or a value sentinel.
Examples
Input:
tree=[3,5,1,6,2,0,8,null,null,7,4]; p=node 5, q=node 4
Output:original node 5A requested node can itself be the ancestor.
Input:
tree=[1,1,1]; p=left child, q=external new Node(1)
Output:nullEqual values do not establish membership.
Input:
p=q=an existing leaf
Output:that leaf identitySelf-ancestor semantics still require presence.
Before you start
- Node identity versus equal values
- Parent discovery and root-to-node ancestor paths
Recognize the structure
The common ancestor deepest from the root is the first shared node encountered walking upward from either target. Build parent links in auxiliary identity state without writing any links into the input.
Try before revealing
Hint 1
Can an equal-valued external object count as a target?
Hint 2
Record actual parents while traversing until both identities are found.
Hint 3
Mark p’s upward chain, then return the first marked identity on q’s upward chain.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Find two root-to-target paths
Recursively search by object identity, retaining each successful root path. If either search fails, return null. Otherwise compare the two path prefixes and retain the last equal object. For targets 5 and 4, paths [3,5] and [3,5,2,4] share their last prefix node 5. This is O(n) work but recursive depth is unsafe for the full bound.
Improve the baseline
Discover parents until membership is known
Record root→null in IdentityHashMap and traverse with an explicit stack. Adding a child records a complete parent path, even before that child is popped. Stop discovery once both target keys are present.
Reject absent or null targets
Use containsKey, not parent.get()!=null: the present root deliberately maps to null. If traversal ends without both keys, return null.
Walk to the first shared ancestor
Insert every identity on p’s parent chain into an identity set. Walk q upward; the first set member is the deepest shared ancestor, including either target itself.
Why it is correct
Parent invariant
Every recorded node belongs to the tree and maps to its actual parent; all ancestors up to root are already recorded when a child is added.
Membership correctness
The proper-tree traversal can discover every reachable node. Missing keys after exhaustion prove absence; identical target references still need their one key to be discovered.
Lowest intersection
Common ancestors form a suffix of each upward chain. Walking q upward encounters its deepest shared ancestor before any higher shared ancestor; membership in p’s set is exactly the common-ancestor condition.
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; }
}
public static Node lca(Node root, Node p, Node q) {
if (root == null || p == null || q == null) return null;
IdentityHashMap<Node,Node> parent = new IdentityHashMap<>();
ArrayDeque<Node> stack = new ArrayDeque<>();
parent.put(root,null); stack.push(root);
while (!stack.isEmpty() && (!parent.containsKey(p) || !parent.containsKey(q))) {
Node node = stack.pop();
if (node.right != null) { parent.put(node.right,node); stack.push(node.right); }
if (node.left != null) { parent.put(node.left,node); stack.push(node.left); }
}
if (!parent.containsKey(p) || !parent.containsKey(q)) return null;
Set<Node> ancestors = Collections.newSetFromMap(new IdentityHashMap<>());
for (Node node = p; node != null; node = parent.get(node)) ancestors.add(node);
for (Node node = q; node != null; node = parent.get(node)) if (ancestors.contains(node)) return node;
return null;
}
private static boolean path(Node node, Node target, List<Node> result) {
if (node == null) return false;
result.add(node);
if (node == target || path(node.left,target,result) || path(node.right,target,result)) return true;
result.remove(result.size()-1); return false;
}
public static Node baseline(Node root, Node p, Node q) {
if (p == null || q == null) return null;
List<Node> a = new ArrayList<>(), b = new ArrayList<>();
if (!path(root,p,a) || !path(root,q,b)) return null;
Node result = null;
for (int i = 0; i < Math.min(a.size(),b.size()) && a.get(i) == b.get(i); i++) result = a.get(i);
return result;
}
}
Read the meaningful blocks
IdentityHashMap makes the contract explicit
Current Node has reference equality, but identity containers also remain correct if value equality is later introduced.
Root membership differs from a missing map entry
Both get(root) and get(external) can return null; containsKey distinguishes them.
Account for auxiliary parent storage
This nonrecursive method intentionally uses O(n) parent state; it is not an O(h)-space recursive LCA claim.
Complexity
Worst-case O(n) expected time under the identity-hash table model and O(n) auxiliary parent/ancestor/frontier storage. Early discovery can reduce work, but absent targets may require visiting the full tree. Returned output is one original reference or null.
The two-path baseline takes O(n) time and O(h) path/call storage, with recursive-stack risk. Binary lifting or Euler-tour indexes amortize many queries at additional preprocessing/storage cost.
Exact-state walkthroughs
Reveal normal and boundary traces
A target can be its own common ancestor
Input: {"tree":[3,5,1,6,2,0,8,null,null,7,4],"p":"T1","q":"T8"} · LCA identity: "T1"
Step 1 of 11: Record root membership separately from its null parent.
A root key with null parent is present. Missing targets have no key. Parent records are auxiliary, not stored in the source nodes.
Phase: initial. Current identity: null.
Original objects — unchanged source edges
- T0: 3left → T1right → T2
- T1: 5left → T3right → T4
- T2: 1left → T5right → T6
- T3: 6left → nullright → null
- T4: 2left → T7right → T8
- T5: 0left → nullright → null
- T6: 8left → nullright → null
- T7: 7left → nullright → null
- T8: 4left → nullright → null
Requested references: T1 and T8. An external label is an object outside the tree, even when its value matches.
Verified parent records — auxiliary identity map
- T0 → null
Discovery stack — top at right
- T0
Marked upward ancestors of p
Empty.
A recorded root with null parent is present; an external object has no key. Parent records do not modify source edges.
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":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}] |
| root | "T0" |
| p | "T1" |
| q | "T8" |
| parent | [{"child":"T0","parent":null}] |
| pending | ["T0"] |
| ancestors | [] |
| phase | "initial" |
| current | 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 public static Node lca(Node root, Node p, Node q) { 9 if (root == null || p == null || q == null) return null; 10 IdentityHashMap<Node,Node> parent = new IdentityHashMap<>(); 11 ArrayDeque<Node> stack = new ArrayDeque<>(); 12 parent.put(root,null); stack.push(root); 13 while (!stack.isEmpty() && (!parent.containsKey(p) || !parent.containsKey(q))) { 14 Node node = stack.pop(); 15 if (node.right != null) { parent.put(node.right,node); stack.push(node.right); } 16 if (node.left != null) { parent.put(node.left,node); stack.push(node.left); } 17 } 18 if (!parent.containsKey(p) || !parent.containsKey(q)) return null; 19 Set<Node> ancestors = Collections.newSetFromMap(new IdentityHashMap<>()); 20 for (Node node = p; node != null; node = parent.get(node)) ancestors.add(node); 21 for (Node node = q; node != null; node = parent.get(node)) if (ancestors.contains(node)) return node; 22 return null; 23 } 24 private static boolean path(Node node, Node target, List<Node> result) { 25 if (node == null) return false; 26 result.add(node); 27 if (node == target || path(node.left,target,result) || path(node.right,target,result)) return true; 28 result.remove(result.size()-1); return false; 29 } 30 public static Node baseline(Node root, Node p, Node q) { 31 if (p == null || q == null) return null; 32 List<Node> a = new ArrayList<>(), b = new ArrayList<>(); 33 if (!path(root,p,a) || !path(root,q,b)) return null; 34 Node result = null; 35 for (int i = 0; i < Math.min(a.size(),b.size()) && a.get(i) == b.get(i); i++) result = a.get(i); 36 return result; 37 } 38 } 39
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Record root membership separately from its null parent.
A root key with null parent is present. Missing targets have no key. Parent records are auxiliary, not stored in the source nodes.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null}]- pending
["T0"]- ancestors
[]- phase
"initial"- current
null
- Discover child identities and their complete parent chains.
Recording a child proves its membership before it is popped; all of its ancestors already have parent records.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
["T2","T1"]- ancestors
[]- phase
"discover"- current
"T0"
- Discover child identities and their complete parent chains.
Recording a child proves its membership before it is popped; all of its ancestors already have parent records.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"},{"child":"T4","parent":"T1"},{"child":"T3","parent":"T1"}]- pending
["T2","T4","T3"]- ancestors
[]- phase
"discover"- current
"T1"
- Discover child identities and their complete parent chains.
Recording a child proves its membership before it is popped; all of its ancestors already have parent records.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"},{"child":"T4","parent":"T1"},{"child":"T3","parent":"T1"}]- pending
["T2","T4"]- ancestors
[]- phase
"discover"- current
"T3"
- Discover child identities and their complete parent chains.
Recording a child proves its membership before it is popped; all of its ancestors already have parent records.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"},{"child":"T4","parent":"T1"},{"child":"T3","parent":"T1"},{"child":"T8","parent":"T4"},{"child":"T7","parent":"T4"}]- pending
["T2","T8","T7"]- ancestors
[]- phase
"discover"- current
"T4"
- Mark one ancestor on p’s upward chain.
Membership uses original object identities, not values. Root is its own ancestor.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"},{"child":"T4","parent":"T1"},{"child":"T3","parent":"T1"},{"child":"T8","parent":"T4"},{"child":"T7","parent":"T4"}]- pending
["T2","T8","T7"]- ancestors
["T1"]- phase
"mark"- current
"T1"
- Mark one ancestor on p’s upward chain.
Membership uses original object identities, not values. Root is its own ancestor.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"},{"child":"T4","parent":"T1"},{"child":"T3","parent":"T1"},{"child":"T8","parent":"T4"},{"child":"T7","parent":"T4"}]- pending
["T2","T8","T7"]- ancestors
["T1","T0"]- phase
"mark"- current
"T0"
- Walk q upward to the first marked identity.
The first shared identity is deepest on q’s ancestor chain and therefore the lowest common ancestor.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"},{"child":"T4","parent":"T1"},{"child":"T3","parent":"T1"},{"child":"T8","parent":"T4"},{"child":"T7","parent":"T4"}]- pending
["T2","T8","T7"]- ancestors
["T1","T0"]- phase
"intersect"- current
"T8"- found
false
- Walk q upward to the first marked identity.
The first shared identity is deepest on q’s ancestor chain and therefore the lowest common ancestor.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"},{"child":"T4","parent":"T1"},{"child":"T3","parent":"T1"},{"child":"T8","parent":"T4"},{"child":"T7","parent":"T4"}]- pending
["T2","T8","T7"]- ancestors
["T1","T0"]- phase
"intersect"- current
"T4"- found
false
- Walk q upward to the first marked identity.
The first shared identity is deepest on q’s ancestor chain and therefore the lowest common ancestor.
- treeNodes
[{"id":"T0","value":3,"left":"T1","right":"T2"},{"id":"T1","value":5,"left":"T3","right":"T4"},{"id":"T2","value":1,"left":"T5","right":"T6"},{"id":"T3","value":6,"left":null,"right":null},{"id":"T4","value":2,"left":"T7","right":"T8"},{"id":"T5","value":0,"left":null,"right":null},{"id":"T6","value":8,"left":null,"right":null},{"id":"T7","value":7,"left":null,"right":null},{"id":"T8","value":4,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T8"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"},{"child":"T4","parent":"T1"},{"child":"T3","parent":"T1"},{"child":"T8","parent":"T4"},{"child":"T7","parent":"T4"}]- pending
["T2","T8","T7"]- ancestors
["T1","T0"]- phase
"intersect"- current
"T1"- found
true
- 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
"T1"
Same values do not prove external membership
Input: {"tree":[1,1,1],"p":"T1","q":"external"} · LCA identity: null
Step 1 of 6: Record root membership separately from its null parent.
A root key with null parent is present. Missing targets have no key. Parent records are auxiliary, not stored in the source nodes.
Phase: initial. Current identity: null.
Original objects — unchanged source edges
- T0: 1left → T1right → T2
- T1: 1left → nullright → null
- T2: 1left → nullright → null
Requested references: T1 and external. An external label is an object outside the tree, even when its value matches.
Verified parent records — auxiliary identity map
- T0 → null
Discovery stack — top at right
- T0
Marked upward ancestors of p
Empty.
A recorded root with null parent is present; an external object has no key. Parent records do not modify source edges.
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":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}] |
| root | "T0" |
| p | "T1" |
| q | "external" |
| parent | [{"child":"T0","parent":null}] |
| pending | ["T0"] |
| ancestors | [] |
| phase | "initial" |
| current | 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 public static Node lca(Node root, Node p, Node q) { 9 if (root == null || p == null || q == null) return null; 10 IdentityHashMap<Node,Node> parent = new IdentityHashMap<>(); 11 ArrayDeque<Node> stack = new ArrayDeque<>(); 12 parent.put(root,null); stack.push(root); 13 while (!stack.isEmpty() && (!parent.containsKey(p) || !parent.containsKey(q))) { 14 Node node = stack.pop(); 15 if (node.right != null) { parent.put(node.right,node); stack.push(node.right); } 16 if (node.left != null) { parent.put(node.left,node); stack.push(node.left); } 17 } 18 if (!parent.containsKey(p) || !parent.containsKey(q)) return null; 19 Set<Node> ancestors = Collections.newSetFromMap(new IdentityHashMap<>()); 20 for (Node node = p; node != null; node = parent.get(node)) ancestors.add(node); 21 for (Node node = q; node != null; node = parent.get(node)) if (ancestors.contains(node)) return node; 22 return null; 23 } 24 private static boolean path(Node node, Node target, List<Node> result) { 25 if (node == null) return false; 26 result.add(node); 27 if (node == target || path(node.left,target,result) || path(node.right,target,result)) return true; 28 result.remove(result.size()-1); return false; 29 } 30 public static Node baseline(Node root, Node p, Node q) { 31 if (p == null || q == null) return null; 32 List<Node> a = new ArrayList<>(), b = new ArrayList<>(); 33 if (!path(root,p,a) || !path(root,q,b)) return null; 34 Node result = null; 35 for (int i = 0; i < Math.min(a.size(),b.size()) && a.get(i) == b.get(i); i++) result = a.get(i); 36 return result; 37 } 38 } 39
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Record root membership separately from its null parent.
A root key with null parent is present. Missing targets have no key. Parent records are auxiliary, not stored in the source nodes.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"external"- parent
[{"child":"T0","parent":null}]- pending
["T0"]- ancestors
[]- phase
"initial"- current
null
- Discover child identities and their complete parent chains.
Recording a child proves its membership before it is popped; all of its ancestors already have parent records.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"external"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
["T2","T1"]- ancestors
[]- phase
"discover"- current
"T0"
- Discover child identities and their complete parent chains.
Recording a child proves its membership before it is popped; all of its ancestors already have parent records.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"external"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
["T2"]- ancestors
[]- phase
"discover"- current
"T1"
- Discover child identities and their complete parent chains.
Recording a child proves its membership before it is popped; all of its ancestors already have parent records.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"external"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
[]- ancestors
[]- phase
"discover"- current
"T2"
- Reject absent requested identities after discovery exhausts.
An external equal-valued object is still absent. Both targets must be present, including p==q.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"external"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
[]- ancestors
[]- phase
"absent"- current
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
null
Identical present targets
Input: {"tree":[1,1,1],"p":"T1","q":"T1"} · LCA identity: "T1"
Step 1 of 6: Record root membership separately from its null parent.
A root key with null parent is present. Missing targets have no key. Parent records are auxiliary, not stored in the source nodes.
Phase: initial. Current identity: null.
Original objects — unchanged source edges
- T0: 1left → T1right → T2
- T1: 1left → nullright → null
- T2: 1left → nullright → null
Requested references: T1 and T1. An external label is an object outside the tree, even when its value matches.
Verified parent records — auxiliary identity map
- T0 → null
Discovery stack — top at right
- T0
Marked upward ancestors of p
Empty.
A recorded root with null parent is present; an external object has no key. Parent records do not modify source edges.
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":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}] |
| root | "T0" |
| p | "T1" |
| q | "T1" |
| parent | [{"child":"T0","parent":null}] |
| pending | ["T0"] |
| ancestors | [] |
| phase | "initial" |
| current | 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 public static Node lca(Node root, Node p, Node q) { 9 if (root == null || p == null || q == null) return null; 10 IdentityHashMap<Node,Node> parent = new IdentityHashMap<>(); 11 ArrayDeque<Node> stack = new ArrayDeque<>(); 12 parent.put(root,null); stack.push(root); 13 while (!stack.isEmpty() && (!parent.containsKey(p) || !parent.containsKey(q))) { 14 Node node = stack.pop(); 15 if (node.right != null) { parent.put(node.right,node); stack.push(node.right); } 16 if (node.left != null) { parent.put(node.left,node); stack.push(node.left); } 17 } 18 if (!parent.containsKey(p) || !parent.containsKey(q)) return null; 19 Set<Node> ancestors = Collections.newSetFromMap(new IdentityHashMap<>()); 20 for (Node node = p; node != null; node = parent.get(node)) ancestors.add(node); 21 for (Node node = q; node != null; node = parent.get(node)) if (ancestors.contains(node)) return node; 22 return null; 23 } 24 private static boolean path(Node node, Node target, List<Node> result) { 25 if (node == null) return false; 26 result.add(node); 27 if (node == target || path(node.left,target,result) || path(node.right,target,result)) return true; 28 result.remove(result.size()-1); return false; 29 } 30 public static Node baseline(Node root, Node p, Node q) { 31 if (p == null || q == null) return null; 32 List<Node> a = new ArrayList<>(), b = new ArrayList<>(); 33 if (!path(root,p,a) || !path(root,q,b)) return null; 34 Node result = null; 35 for (int i = 0; i < Math.min(a.size(),b.size()) && a.get(i) == b.get(i); i++) result = a.get(i); 36 return result; 37 } 38 } 39
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Record root membership separately from its null parent.
A root key with null parent is present. Missing targets have no key. Parent records are auxiliary, not stored in the source nodes.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T1"- parent
[{"child":"T0","parent":null}]- pending
["T0"]- ancestors
[]- phase
"initial"- current
null
- Discover child identities and their complete parent chains.
Recording a child proves its membership before it is popped; all of its ancestors already have parent records.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T1"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
["T2","T1"]- ancestors
[]- phase
"discover"- current
"T0"
- Mark one ancestor on p’s upward chain.
Membership uses original object identities, not values. Root is its own ancestor.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T1"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
["T2","T1"]- ancestors
["T1"]- phase
"mark"- current
"T1"
- Mark one ancestor on p’s upward chain.
Membership uses original object identities, not values. Root is its own ancestor.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T1"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
["T2","T1"]- ancestors
["T1","T0"]- phase
"mark"- current
"T0"
- Walk q upward to the first marked identity.
The first shared identity is deepest on q’s ancestor chain and therefore the lowest common ancestor.
- treeNodes
[{"id":"T0","value":1,"left":"T1","right":"T2"},{"id":"T1","value":1,"left":null,"right":null},{"id":"T2","value":1,"left":null,"right":null}]- root
"T0"- p
"T1"- q
"T1"- parent
[{"child":"T0","parent":null},{"child":"T2","parent":"T0"},{"child":"T1","parent":"T0"}]- pending
["T2","T1"]- ancestors
["T1","T0"]- phase
"intersect"- current
"T1"- found
true
- 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
"T1"
Empty tree and null request
Input: {"tree":[],"p":null,"q":"external"} · LCA identity: null
Step 1 of 2: Reject an empty tree or null requested identity.
Equal values cannot replace object membership. No tree links are changed.
Phase: absent. Current identity: null.
Original objects — unchanged source edges
Empty tree.
Requested references: null and external. An external label is an object outside the tree, even when its value matches.
Verified parent records — auxiliary identity map
Empty.
Discovery stack — top at right
Empty.
Marked upward ancestors of p
Empty.
A recorded root with null parent is present; an external object has no key. Parent records do not modify source edges.
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 | [] |
| root | null |
| p | null |
| q | "external" |
| parent | [] |
| pending | [] |
| ancestors | [] |
| phase | "absent" |
| current | 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 public static Node lca(Node root, Node p, Node q) { 9 if (root == null || p == null || q == null) return null; 10 IdentityHashMap<Node,Node> parent = new IdentityHashMap<>(); 11 ArrayDeque<Node> stack = new ArrayDeque<>(); 12 parent.put(root,null); stack.push(root); 13 while (!stack.isEmpty() && (!parent.containsKey(p) || !parent.containsKey(q))) { 14 Node node = stack.pop(); 15 if (node.right != null) { parent.put(node.right,node); stack.push(node.right); } 16 if (node.left != null) { parent.put(node.left,node); stack.push(node.left); } 17 } 18 if (!parent.containsKey(p) || !parent.containsKey(q)) return null; 19 Set<Node> ancestors = Collections.newSetFromMap(new IdentityHashMap<>()); 20 for (Node node = p; node != null; node = parent.get(node)) ancestors.add(node); 21 for (Node node = q; node != null; node = parent.get(node)) if (ancestors.contains(node)) return node; 22 return null; 23 } 24 private static boolean path(Node node, Node target, List<Node> result) { 25 if (node == null) return false; 26 result.add(node); 27 if (node == target || path(node.left,target,result) || path(node.right,target,result)) return true; 28 result.remove(result.size()-1); return false; 29 } 30 public static Node baseline(Node root, Node p, Node q) { 31 if (p == null || q == null) return null; 32 List<Node> a = new ArrayList<>(), b = new ArrayList<>(); 33 if (!path(root,p,a) || !path(root,q,b)) return null; 34 Node result = null; 35 for (int i = 0; i < Math.min(a.size(),b.size()) && a.get(i) == b.get(i); i++) result = a.get(i); 36 return result; 37 } 38 } 39
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Reject an empty tree or null requested identity.
Equal values cannot replace object membership. No tree links are changed.
- treeNodes
[]- root
null- p
null- q
"external"- parent
[]- pending
[]- ancestors
[]- phase
"absent"- current
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
null
Test the contract
Input:
Either target null
Output:nullNo valid pair.
Input:
One or both external targets
Output:nullMembership required.
Input:
p==q and present
Output:same identitySelf ancestry.
Input:
100,000 equal-valued nodes in a chain
Output:shallower requested identityIdentity and depth, not values.
Common mistakes and counterexamples
Compare target values
Counterexample: Repeated 1s and an external Node(1) are distinct identities.
Compare object references and verify reachability.
Assume both targets exist
Counterexample: A one-target recursive result can be falsely reported as their LCA.
Require both membership keys before intersecting ancestors.
Use parent.get(target)!=null as membership
Counterexample: The root is present but maps to null.
Use containsKey.
Follow-ups
Answer many LCA queries.
Consider binary lifting or an Euler tour with range-minimum queries. Include preprocessing, storage, query complexity and missing-target membership in the design.
Use a strict BST.
Value-guided descent can find the split point under unique-key and guaranteed-membership contracts. If membership remains optional, independently verify targets; equal values do not replace reference identity.
Return the full path between targets.
Join the two parent-chain prefixes at the LCA, reversing the q-side segment. Preserve identity order and account for O(path length) output.
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 · 164/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Related foundations
- Tree foundations: structure, depth, and traversal state
- DFS: traverse components with explicit state meaning