C++ program to find lowest common ancestor in a binary tree














































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 #include <bits/stdc++.h> 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; }

More Articles of Mandeep Sheoran:

Name Views Likes
C++ program to insert an element into binary tree 6884 19
C++ program to find an element into binary tree 815 16
C++ std::is_void 615 15
C++ program to find the closest element in binary search tree 1015 19
C++ program to replace every element with the least greater element on its right 615 12
C++ program to delete an element into binary tree 825 24
C++ program to find maximum element between two nodes of binary search tree 740 20
C++ std::remove_copy_if with std::vectors 597 11
C++ program to print duplicate elements from the binary search tree 3097 15
C++ program to find depth of the deepest odd level node in binary tree 614 23
C++ program to remove duplicate elements from the binary search tree 1755 20
C++ std::rotate_copy with std::vector 584 14
C++ std::copy_n with std::vector 671 22
C++ std::copy_if with std::vector 1660 18
C++ program to print all the elements of binary search tree 7983 22
C++ std::reverse_copy with std::list 640 18
C++ program to print all the elements of binary tree 1251 18
C++ program to print all full nodes in a binary tree 609 25
C++ program to find sink odd nodes in binary tree 610 15
C++ std::is_copy_assignable 641 22
C++ program to check whether a binary tree is a full binary tree or not using recursion 664 19
C++ std::is_copy_constructible 663 27
C++ program to delete an element into binary search tree 3197 18
C++ std::reverse_copy with std::vector 526 18
C++ std::rotate with std::vector 798 15
C++ program to check for symmetric binary tree using recursion 630 25
C++ program to maximum sum from a tree with adjacent levels not allowed 593 15
C++ std::copy_n with std::list 641 21
C++ program to check if two trees are identical using recursion 587 15
C++ std::copy_n 966 21
C++ std::copy_if with std::list 1131 19
C++ program to print the nodes at odd levels of a tree 601 13
C++ program to find lowest common ancestor in a binary tree 719 29
C++ program to find depth of the deepest odd level leaf node 529 13
C++ std::remove_copy_if with std::list 718 20
C++ program to add all greater values to every node in a given binary search tree 683 15

Comments