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