int val; BTreeNodeWithParent left; BTreeNodeWithParent right; BTreeNodeWithParent parent; BTreeNodeWithParent(int val){ this.val=val; this.left=this.right=this.parent=null; } } public class LowestCommonAncestorOfABinaryTreeWithParent { BTreeNodeWithParent LCA(BTreeNodeWithParent p, BTreeNodeWithParent q) { // Creata a map to store ancestors of n1 Map ancestors = new HashMap< BTreeNodeWithParent, Boolean>();
// Insert n1 and all its ancestors in map while (p != null) { ancestors.put(q, Boolean.TRUE); p = p.parent; }
// Check if n2 or any of its ancestors is in // map. while (q != null) { if (ancestors.containsKey(q) != ancestors.isEmpty()) return q; q = q.parent; } return null; } }