Data Structure Binary Tree: Lowest Common Ancestor in a Binary Tree

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <stack>
 6 #include <string>
 7 #include <fstream>
 8 #include <map>
 9 using namespace std;
10 
11 struct node {
12     int data;
13     struct node *left, *right;
14     node() : data(0), left(NULL), right(NULL) { }
15     node(int d) : data(d), left(NULL), right(NULL) { }
16 };
17 
18 bool findpath(node *root, vector<int> &path, int n) {
19     if (!root) return false;
20     path.push_back(root->data);
21     if (root->data == n) return true;
22     if (root->left && findpath(root->left, path, n) || root->right && findpath(root->right, path, n)) return true;
23     path.pop_back();
24     return false;
25 }
26 
27 int LCA(node *root, int n1, int n2) {
28     if (!root) return -1;
29     vector<int> path1, path2;
30     if (!findpath(root, path1, n1) || !findpath(root, path2, n2)) return -1;
31     int i = 0;
32     for (; i < path1.size() && i < path2.size(); i++) {
33         if (path1[i] != path2[i]) break;
34     }
35     return path1[i-1];
36 }
37 
38 int main() {
39     node *root = new node(1);
40     root->left = new node(2);
41     root->right = new node(3);
42     root->left->left = new node(4);
43     root->left->right = new node(5);
44     root->right->left = new node(6);
45     root->right->right = new node(7);
46     cout << "LCA(4, 5) is " << LCA(root, 4, 5) << endl;
47     cout << "LCA(4, 6) is " << LCA(root, 4, 6) << endl;
48     cout << "LCA(3, 4) is " << LCA(root, 3, 4) << endl;
49     cout << "LCA(2, 4) is " << LCA(root, 2, 4) << endl;
50     return 0;
51 }