Symantec

www.symantec.com
Engaged Employer

## Interview Question

Interview Culver City, CA

# find lowest common ancestor of 2 nodes in a binary tree

Tags:

0

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
0

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
1

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

double&#039;o on Oct 19, 2012