Skip to content

Commit 0675be6

Browse files
roydevashishroydevashish
committed
Completed BST - 2
1 parent 69b5cb0 commit 0675be6

File tree

5 files changed

+800
-0
lines changed

5 files changed

+800
-0
lines changed

‎F33BST-2/BSTClass.cpp‎

Lines changed: 211 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,211 @@
1+
/*
2+
Title: BST Class
3+
4+
Problem statement
5+
Implement the BST class which includes following functions -
6+
1. insert -
7+
Given an element, insert that element in the BST at the correct position. If element is equal to
8+
the data of the node, insert it in the left subtree.
9+
10+
2. search
11+
Given an element, find if that is present in BST or not. Return true or false.
12+
13+
3. delete -
14+
Given an element, remove that element from the BST. If the element which is to be deleted has both
15+
children, replace that with the minimum element from right sub-tree.
16+
17+
4. printTree (recursive) -
18+
Print the BST in in the following format -
19+
For printing a node with data N, you need to follow the exact format -
20+
N:L:x,R:y
21+
22+
where, N is data of any node present in the binary tree. x and y are the values of left and right
23+
child of node N. Print the children only if it is not null.
24+
There is no space in between.
25+
You need to print all nodes in the recursive format in different lines.
26+
27+
Sample Input 1:
28+
6
29+
1 2
30+
1 3
31+
1 1
32+
4
33+
2 2
34+
4
35+
36+
Sample Output 1:
37+
2:L:1,R:3
38+
1:
39+
3:
40+
3:L:1,
41+
1:
42+
43+
Explanation for sample Input 1:
44+
Explanation: The first line 6 indicates that there are 6 operations to be performed on the BST.
45+
The subsequent lines are the operations, which can be understood as follows:
46+
1 2: Insert 2 into the BST.
47+
48+
1 3: Insert 3 into the BST.
49+
50+
1 1: Insert 1 into the BST.
51+
52+
4: Print the BST in the specified format.
53+
54+
2 2: Search for 2 in the BST.
55+
56+
4: Print the BST in the specified format.
57+
*/
58+
59+
#include<iostream>
60+
#include<queue>
61+
using namespace std;
62+
63+
template <typename T>
64+
class BinaryTreeNode {
65+
public:
66+
T data;
67+
BinaryTreeNode<T> *left;
68+
BinaryTreeNode<T> *right;
69+
70+
BinaryTreeNode(T data) {
71+
this->data = data;
72+
left = NULL;
73+
right = NULL;
74+
}
75+
};
76+
77+
class BST {
78+
private:
79+
BinaryTreeNode<int> * root;
80+
81+
public:
82+
BST() {
83+
root = NULL;
84+
}
85+
86+
/*----------------- Public Functions of BST -----------------*/
87+
BinaryTreeNode<int> * removeHelper(BinaryTreeNode<int> * node, int data) {
88+
if(node == NULL) {
89+
return NULL;
90+
}
91+
92+
if(data < node->data) {
93+
node->left = removeHelper(node->left, data);
94+
return root;
95+
} else if(data > node->data) {
96+
node->right = removeHelper(node->right, data);
97+
return node;
98+
} else {
99+
if(node->left == NULL && node->right == NULL) {
100+
return NULL;
101+
} else if(node->left == NULL) {
102+
return node->right;
103+
} else if(node->right == NULL) {
104+
return node->left;
105+
} else {
106+
BinaryTreeNode<int> * minNode = node->right;
107+
while(minNode->left != NULL) {
108+
minNode = minNode->left;
109+
}
110+
111+
node->data = minNode->data;
112+
node->right = removeHelper(node->right, minNode->data);
113+
return node;
114+
}
115+
}
116+
}
117+
118+
void remove(int data) {
119+
this->root = removeHelper(this->root, data);
120+
}
121+
122+
void printHelper(BinaryTreeNode<int> * node) {
123+
if(node == NULL) {
124+
return;
125+
}
126+
127+
cout << node->data << ":";
128+
if(node->left != NULL) {
129+
cout << "L:" << node->left->data << ",";
130+
}
131+
132+
if(node->right != NULL) {
133+
cout << "R:" << node->right->data;
134+
}
135+
cout << endl;
136+
137+
printHelper(node->left);
138+
printHelper(node->right);
139+
}
140+
141+
void print() {
142+
printHelper(this->root);
143+
}
144+
145+
BinaryTreeNode<int> * insertHelper(BinaryTreeNode<int> * node, int data) {
146+
if(node == NULL) {
147+
BinaryTreeNode<int> * newNode = new BinaryTreeNode<int>(data);
148+
return newNode;
149+
}
150+
151+
if(data <= node->data) {
152+
node->left = insertHelper(node->left, data);
153+
}
154+
155+
if(data > node->data) {
156+
node->right = insertHelper(node->right, data);
157+
}
158+
159+
return node;
160+
}
161+
162+
void insert(int data) {
163+
this->root = insertHelper(this->root, data);
164+
}
165+
166+
bool searchHelper(BinaryTreeNode<int> * node, int data) {
167+
if(node == NULL) {
168+
return false;
169+
}
170+
171+
if(node->data == data) {
172+
return true;
173+
}
174+
175+
if(data < node->data) {
176+
return searchHelper(node->left, data);
177+
} else if(data > node->data) {
178+
return searchHelper(node->right, data);
179+
}
180+
}
181+
182+
bool search(int data) {
183+
return searchHelper(this->root, data);
184+
}
185+
};
186+
187+
int main() {
188+
BST *tree = new BST();
189+
int choice, input, q;
190+
cin >> q;
191+
while(q--) {
192+
cin >> choice;
193+
switch(choice) {
194+
case 1:
195+
cin >> input;
196+
tree->insert(input);
197+
break;
198+
case 2:
199+
cin >> input;
200+
tree->remove(input);
201+
break;
202+
case 3:
203+
cin >> input;
204+
cout << ((tree->search(input)) ? "true\n" : "false\n");
205+
break;
206+
default:
207+
tree->print();
208+
break;
209+
}
210+
}
211+
}

‎F33BST-2/FindPathInBST.cpp‎

Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,135 @@
1+
/*
2+
Title: Find Path in BST
3+
4+
Problem statement
5+
Given a BST and an integer k. Find and return the path from the node with data k and root (if a
6+
node with data k is present in given BST) in a list. Return empty list otherwise.
7+
Note: Assume that BST contains all unique elements.
8+
9+
Detailed explanation ( Input/output format, Notes, Images )
10+
Input Format :
11+
The first line of input contains data of the nodes of the tree in level order form. The data of the
12+
nodes of the tree is separated by space. If any node does not have left or right child, take -1 in
13+
its place. Since -1 is used as an indication whether the left or right nodes exist, therefore, it
14+
will not be a part of the data of any node.
15+
The following line of input contains an integer, that denotes the value of k.
16+
17+
Output Format :
18+
The first line and only line of output prints the data of the nodes in the path from node k to root.
19+
The data of the nodes is separated by single space.
20+
21+
Constraints:
22+
Time Limit: 1 second
23+
24+
Sample Input 1:
25+
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
26+
2
27+
28+
Sample Output 1:
29+
2 5 8
30+
*/
31+
32+
#include<iostream>
33+
#include<queue>
34+
#include<vector>
35+
using namespace std;
36+
37+
template <typename T>
38+
class BinaryTreeNode {
39+
public:
40+
T data;
41+
BinaryTreeNode<T> *left;
42+
BinaryTreeNode<T> *right;
43+
44+
BinaryTreeNode(T data) {
45+
this->data = data;
46+
left = NULL;
47+
right = NULL;
48+
}
49+
~BinaryTreeNode() {
50+
if (left) delete left;
51+
if (right) delete right;
52+
}
53+
};
54+
55+
void getPathHelper(BinaryTreeNode<int> *root , int data, vector<int> **output) {
56+
if(root == NULL) {
57+
return;
58+
}
59+
60+
getPathHelper(root->left, data, &*output);
61+
vector<int> *tempLeft = *output;
62+
if(tempLeft != NULL) {
63+
tempLeft->push_back(root->data);
64+
return;
65+
}
66+
67+
getPathHelper(root->right, data, &*output);
68+
vector<int> *tempRight = *output;
69+
if(tempRight != NULL) {
70+
tempRight->push_back(root->data);
71+
return;
72+
}
73+
74+
if(root->data == data) {
75+
vector<int> *temp = *output;
76+
temp->push_back(root->data);
77+
return;
78+
}
79+
80+
return;
81+
}
82+
83+
vector<int>* getPath(BinaryTreeNode<int> *root , int data) {
84+
vector<int> *output;
85+
getPathHelper(root, data, &output);
86+
return output;
87+
}
88+
89+
90+
BinaryTreeNode<int> *takeInput() {
91+
int rootData;
92+
cin >> rootData;
93+
if(rootData == -1) {
94+
return NULL;
95+
}
96+
97+
BinaryTreeNode<int> *root = new BinaryTreeNode<int>(rootData);
98+
queue<BinaryTreeNode<int> *> q;
99+
q.push(root);
100+
while(!q.empty()) {
101+
BinaryTreeNode<int> *currentNode = q.front();
102+
q.pop();
103+
int leftChild, rightChild;
104+
cin >> leftChild;
105+
if(leftChild != -1) {
106+
BinaryTreeNode<int> *leftNode = new BinaryTreeNode<int>(leftChild);
107+
currentNode->left = leftNode;
108+
q.push(leftNode);
109+
}
110+
cin >> rightChild;
111+
if(rightChild != -1) {
112+
BinaryTreeNode<int> *rightNode =
113+
new BinaryTreeNode<int>(rightChild);
114+
currentNode->right = rightNode;
115+
q.push(rightNode);
116+
}
117+
}
118+
119+
return root;
120+
}
121+
122+
int main() {
123+
BinaryTreeNode<int> *root = takeInput();
124+
int k;
125+
cin >> k;
126+
vector<int> *output = getPath(root, k);
127+
128+
if(output != NULL) {
129+
for(int i = 0; i < output->size(); i++) {
130+
cout << output->at(i) << " ";
131+
}
132+
}
133+
134+
delete root;
135+
}

0 commit comments

Comments
 (0)