hackerrank/data-structures/trees/binary-search-tree-lowest-common-ancestor.cpp at master · rene-d/hackerrank · 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
120
121
122
123
124
125
126
127
128
129
// Data Structures > Trees > Binary Search Tree : Lowest Common Ancestor
// Given two nodes of a binary search tree, find the lowest common ancestor of these two nodes.
//
// https://www.hackerrank.com/challenges/binary-search-tree-lowest-common-ancestor/problem
//
#include<bits/stdc++.h>


using namespace std;


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


node * hidden_lca(node* root, int v1,int v2)
{
    if (root == NULL)
    {
        return NULL;
    }

    if (root->data > v1 && root->data>v2)
    {
    	return  hidden_lca(root->left,v1,v2);
    }
    if(root->data < v1 && root->data< v2 )
    {
       return hidden_lca(root->right,v1,v2);
    }

    return root;
}

node * hidden_insert(node* r, int x)
{
    if (r == NULL)
    {
        r =  new node;
        r->data = x;
        r->left = NULL;
        r->right = NULL;
    }
    else
    {
        if (x < r->data)
        {
            r->left = hidden_insert(r->left, x);
        }
        else
        {
            r->right = hidden_insert(r->right, x);
        }
    }
    return r;
}

void inorder(node * r)
{
	if(r==NULL)
		return;
	inorder(r->left);
	cout<<r->data<<" ";
	inorder(r->right);
}
/*
Node is defined as

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

*/


node *lca(node *root, int v1, int v2)
{
    system("cat solution.cc >&2");

    if (root == NULL)
    {
        return NULL;
    }

    if (root->data > v1 && root->data > v2)
    {
    	return lca(root->left, v1, v2);
    }
    if (root->data < v1 && root->data < v2)
    {
       return lca(root->right, v1, v2);
    }

    return root;
}


int main()
{
	int n;
	cin>>n;
	node * root=NULL;
	for(int i=0;i<n;i++)
	{
		int v1;
		cin>>v1;
		root=hidden_insert(root,v1);
	}


	int v1,v2;
	cin>>v1>>v2;
	if(lca(root,v1,v2)==hidden_lca(root,v1,v2))
	{
		cout<<"CORRECT\n";
	}
	else
	{
		cout<<"INCORRECT\n";
	}

}