Code/LCA.cpp at master · sushiljacksparrow/Code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
/*Sushil Kumar Singh */
#include <cassert>
#include <cctype>
#include <cfloat>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <valarray>
#include <vector>
#include <ext/numeric>
#include <ext/hash_map>
#include <ext/hash_set>
#include <ext/algorithm>

using namespace std;
using namespace __gnu_cxx;

#define pb push_back
#define vi vector<int>
#define vii vector<vi>
#define ii pair<int,int>
#define vs vector<string>
#define all(v) (v).begin(), (v).end()
#define For(i,x) for(int i=0;i<x;i++)

struct node
{
	node *left, *right;
	int data;
};

// LCA of a BST
node *LCA_BST(node *r, node *r1, node *r2)
{
	if(r==NULL || r1 == NULL || r2==NULL)
		return NULL;
	if(max(r1->data, r2->data) < r->data)
		return LCA_BST(r->left, r1, r2);
	else if(min(r1->data, r2->data) > r->data)
		return LCA_BST(r->right, r1, r2);
	else
		return r;
}

int count(node *root, node *p, node *q)
{
	if(root==NULL)
		return 0;
	int match = count(root->left, p, q) + count(root->right, p, q);
	if(root == p || root==q)
		return 1+match;
	else
		return match;
}

// LCA of a binary stree

node *LCA(node *r, node *p, node *q)
{
	if(r==NULL || p==NULL || q==NULL)
		return NULL;
	if(r==p || r==q)
		return r;

	int totalMatch = count(r->left, p, q);
	if(totalMatch==1)
		return r;
	if(totalMatch==2)
		return LCA(r->left, p, q);
	else
		return LCA(r->right, p, q);
}

// bottomo up approach

node *LCA_b(node *root, node *p, node *q)
{
	if(root==NULL)
		return root;
	if(root==p || root==q)
		return root;
	node *L = LCA_b(root->left, p, q);
	node *R = LCA_b(root->right, p, q);
	if(L && R)
		return root;
	return L ? L : R;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);


    system("pause");
}