Lowest Common Ancestor of a Binary Tree

Lowest Common Ancestor of a Binary Tree

Problem:Find the lowest common ancestor of two given nodes in the binary tree.

Solution:

1 2 3 4 5 6 7 8

BinaryNode LCA(BinaryNode root, BinaryNode p, BinaryNode q) {   if (root == NULL) return NULL;   if (root == p || root == q) return root;   BinaryNode L = LCA(root.left, p, q);   BinaryNode R = LCA(root.right, p, q);   if (L != NULL && R != NULL) return root;  // if p and q are on both sides   return (L != NULL) ? L : R;  }

Click here for more Programming Interview Questions