fork(1) download
copy 
  1. /* Program to find LCA of n1 and n2 using one traversal of Binary Tree By Gohired.in */
  2. #include <iostream>
  3. using namespace std;
  4.  
  5. struct Node
  6. {
  7. 	struct Node *left, *right;
  8. 	int key;
  9. };
  10.  
  11. Node* newNode(int key)
  12. {
  13. 	Node *temp = new Node;
  14. 	temp->key = key;
  15. 	temp->left = temp->right = NULL;
  16. 	return temp;
  17. }
  18.  
  19. struct Node *findLCA(struct Node* root, int n1, int n2)
  20. {
  21. 	if (root == NULL) return NULL;
  22.  
  23. 	if (root->key == n1 || root->key == n2)
  24. 		return root;
  25.  
  26. 	Node *left_lca = findLCA(root->left, n1, n2);
  27. 	Node *right_lca = findLCA(root->right, n1, n2);
  28. 	if (left_lca && right_lca) return root;
  29.  
  30. 	return (left_lca != NULL)? left_lca: right_lca;
  31. }
  32.  
  33. int main()
  34. {
  35. 	Node * root = newNode(1);
  36. 	root->left = newNode(2);
  37. 	root->right = newNode(3);
  38. 	root->left->left = newNode(4);
  39. 	root->left->right = newNode(5);
  40. 	root->right->left = newNode(6);
  41. 	root->right->right = newNode(7);
  42. 	cout << "LCA(4, 5) = " << findLCA(root, 4, 5)->key<<endl;
  43. 	cout << "LCA(4, 6) = " << findLCA(root, 4, 6)->key<<endl;
  44. 	cout << "LCA(3, 4) = " << findLCA(root, 3, 4)->key<<endl;
  45. 	cout << "LCA(2, 4) = " << findLCA(root, 2, 4)->key<<endl;
  46. 	return 0;
  47. }
  48.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(3, 4) = 1
LCA(2, 4) = 2
https://ideone.com/J7gzfk
Bintree - LCA
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!