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

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 */
return null;

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

/* 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 */
return left;
return right;


You need to Sign In to post your solution.