Interview Question

Interview Culver City, CA

find lowest common ancestor of 2 nodes in a binary tree


Interview Answer

3 Answers


I tried a complicated recursive methods and got stuck. If there is no restriction, we actually could use an hash map to store tree nodes while tracing up the parent nodes of the given nodes. if a common node is found to be parent of the given 2 nodes then print it out

Interview Candidate on Jul 10, 2011

Node lowestCommonAncestor(Node root, Node a, Node b) { if (root.contains(a) && root.contains(b)) { if (root.left != null && root.left.contains(a) && root.left.contains(b)) return lowestCommonAncestor(root.left, a, b); else if (root.right != null && root.right.contains(a) && root.right.contains(b)) return lowestCommonAncestor(root.right, a, b); else return root; } else return null; } boolean contains(Node root, Node x) { if (root == null || x == null) return false; // not needed. Defensive coding if (root == x) return true; if (root.left != null and root.left.contains(x)) return true; if (root.right != null and root.right.contains(x)) return true; return false; }

Anonymous on Jun 28, 2012

int lowestCommonAncestor(Node node, int value1, int value2){ if(node == null) return -1; if(value1 > && value2 > return lowestCommonAncestor(node.right, value1, value2); else if(value1 < && value2 < return lowestCommonAncestor(node.left, value1, value2); else return; }

double&#039;o on Oct 19, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.