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

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