CodingExcercises/LCABinarySearchTree.cpp at master · madhu90/CodingExcercises · 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
/** Construct the following binary search tree:
*			  15
*			/    \
*		  10	  25
*		 /  \	  /  \
*		8	 12	 20   30
*	   / \		/  \
*	 6     9  18    22
* For this tree, find the lowest common ancestors of the following
* pairs of nodes:
* LCA(6,12) = 3
* LCA(10,12) = 5
* LCA(20,6) = 3
* LCA(18,22) = 20
* LCA(30,30) = 30
*/

#include <iostream>
#include <memory>

class Node {
public:
	int data;
	Node* left;
	Node* right;

public:
	Node(int value)
		: data(value), left(nullptr), right(nullptr)
	{
	}
};

class BinarySearchTree
{
private:
	Node* root;

public:
	BinarySearchTree()
	{
		construct();
	}

	~BinarySearchTree()
	{
		destroy(root);
	}

	int findLCA(int x, int y)
	{
		return findLCAHelper(root, x, y);
	}

private:

	void destroy(Node*& rootnode)
	{
		if (rootnode)
		{
			destroy(rootnode->left);
			destroy(rootnode->right);
			delete(rootnode);
			rootnode = nullptr;
		}
	}

	int findLCAHelper(Node* rootnode, int x, int y)
	{
		if (rootnode->data > x && rootnode->data > y)
		{
			return findLCAHelper(rootnode->left, x, y);
		} else if (rootnode->data < x && rootnode->data < y) {
			return findLCAHelper(rootnode->right, x, y);
		} else {
			return rootnode->data;
		}
	}

	void construct()
	{
		root = addNode(root, 15);
		root = addNode(root, 10);
		root = addNode(root, 8);
		root = addNode(root, 6);
		root = addNode(root, 9);
		root = addNode(root, 12);
		root = addNode(root, 25);
		root = addNode(root, 20);
		root = addNode(root, 18);
		root = addNode(root, 22);
		root = addNode(root, 30);
	}

	Node* addNode(Node*& rootnode, int data)
	{
		if (rootnode == nullptr) {
			return new Node(data);
		} else {
			if (rootnode->data > data)
			{
				rootnode->left = addNode(rootnode->left, data);
			} else {
				rootnode->right = addNode(rootnode->right, data);
			}

			return rootnode;
		}
	}
};

int main()
{
	BinarySearchTree obj;
	std::cout << "LCA(6, 12) " << obj.findLCA(6, 12) << std::endl;
	std::cout << "LCA(10, 12) " << obj.findLCA(10, 12) << std::endl;
	std::cout << "LCA(20, 6) " << obj.findLCA(20, 6) << std::endl;
	std::cout << "LCA(18, 22) " << obj.findLCA(18, 22) << std::endl;
	std::cout << "LCA(30, 30) " << obj.findLCA(30, 30) << std::endl;
	return 0;
}