Home Trees Give an algorithm to find the LCA(Least Common Ancestor) of two nodes in a Binary tree.

# Give an algorithm to find the LCA(Least Common Ancestor) of two nodes in a Binary tree.

0 comment

Question: Given the root pointer to a binary tree, find the LCA (Least Common Ancestor) of two nodes in the tree.
Input: Sample Tree (Pointer to node 1 is given). Find LCA of node 5 and 4
Output: Answer = 3

A simple recursive approach can be used to find the LCA (Least common ancestor).

#include<stdio.h>
#include<malloc.h>

struct binaryTreeNode{
int data;
struct binaryTreeNode * left;
struct binaryTreeNode * right;
};

struct binaryTreeNode * LCA(struct binaryTreeNode * root, struct binaryTreeNode * a, struct binaryTreeNode * b)
{
struct binaryTreeNode * left, *right;

// The terminating condition
if(root == NULL)
return root;

// If one of the elements is among the input nodes, then we have got our LCA
if(root == a || root == b)
return root;

// Search in the left sub tree
left = LCA(root -> left, a, b);

// Search in the right sub tree
right = LCA(root -> right, a, b);

if(left && right)
return root;
else
return (left ? left : right)
}


#### You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More