C++ program to find lowest common ancestor in a binary tree
Description:
This Program is to find sink odd nodes in binary tree
For Example:
Input :
The Elements are : 1 ,2 ,3 ,4 ,5 ,6 ,7
1
/ \
2 3
/ \ / \
4 5 6 7
Output :
Enter two no to find lowest common ancestor : 4
6
LCA(4,6) = 1
Program :
//C++ program to find lowest common ancestor in a binary tree
using namespace std;
// tree node
struct Node
{
int data;
Node *left, *right;
};
// returns a new tree Node
Node* newNode(int data)
{
Node* temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
// This function returns pointer to LCA of two given values num1 and num2.
struct Node *LCA(struct Node* root, int num1, int num2)
{
// Base case
if (root == NULL) return NULL;
if (root->data == num1 || root->data == num2)
return root;
// Look for keys in left and right subtrees
Node *left = LCA(root->left, num1, num2);
Node *right = LCA(root->right, num1, num2);
if (left && right) return root;
// Otherwise check if left subtree or right subtree is LCA
return (left != NULL)? left: right;
}
int main()
{
Node * root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
int a,b;
cout<<"Enter two no to find lowest common ancestor : ";
cin>>a>>b;
cout << "LCA("<<a<<","<<b<<") = " << LCA(root, a, b)->data;
return 0;
}
Comments