Find Lowest Common Ancestor in a binary tree
  • Posted: 4 years ago
  • Edit
  • answers (1)
  • views (3550)

You are given a binary tree with the value of two nodes in it. Write an algorithm to find the lowest common ancestor.


Posted Answers


  • Start from root node and move downward.
  • If any node found has either \( p \) or \( p \) as its direct child then it is the LCA.
  • If a node is found with \( p \) in its left(or right) subtree and \( q \) in its right(or left) subtree then it is the LCA.

Time complexity = \( O(n) \).

 
public static Node findLCA(Node root, Node p, Node q){

/* If there is no root */
if(!root)
return null;


/* if either p or q is the root then root is LCA */
if(root == p || root == q)
return root;
else{

/* get LCA of p and q in left subtree */
Node left = findLCA(root.left, p, q);

/* get LCA of p and q in right subtree */
Node right = findLCA(root.right, p, q);

/* if any of p or q is in left subtree and other in right : root is LCA */
if(left & & right)
return root;

/* If left is not null, left is LCA */
elseif(left)
return left;
else
return right;

}
}

You need to Sign In to post your solution.