Interview Question

Software Engineer Interview Culver City, CA

find lowest common ancestor of 2 nodes in a binary tree

Tags:
Answer

Interview Answer

3 Answers

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'o on Oct 19, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.