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

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)
}