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.

by nikoo28
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)
}
0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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