### Find Lowest Common Ancestor in a binary tree node binarytree    Posted: 5 years ago Edit answers (1) views (3967)

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

 Posted: 5 years ago Updated: 5 years ago 0 0 Edit 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; } }