# Binary Search Tree in C/C++ [2]

In the last post we learnt about Binary Search Trees and basic operations like insert and search on them. In this post we’ll learn about some complex operations on them.

##### Implementing Binary Search Tree operations in C/C++
###### Finding Minimum Element
Tree-Minimum (root)1. while (left[root] != NULL)2.   root = left[root]3. return root
###### Finding Maximum Element
Tree-Maximum (root)
1. while (right[root] != NULL)
2.   root = right[root]
3. return root

Note: Given a node in a binary search tree, it is sometimes required to find its successor and predecessor in the sorted order determined by an inorder traversal

###### Inserting into a Binary Search Tree (BST) and saving parent node (predecessor)
Tree-Insert (root, z, parent) // parent is to store parent node
1. if root == NULL
2.   return create(z, parent)
3. if info[root] < z
4.   parent = root
5.   right[root] = Tree-Insert(right[root], z, parent)
6. if info[root] > z
7.   parent = root
8.   left[root] = Tree-Insert(left[root], z, parent)
9  return root
###### Finding Successor
Tree-Successor (x)1. if right[x] != NULL2.   return Tree-Minimum (right[x])3. y = parent[x]4. while y != NULL and x == right[y]5.   do x = y6.     y = parent[y]7. return y
###### Deleting a node from Binary Search Tree (BST) (requires pointer to the parent Node)
Tree-Delete (T, x)
1. if left[x] != NULL && right[x] != NULL //If x (node to be deleted) have both children
2.   z = Tree-Successor (x)
3.   info[x] = info[z]
4.   x = z
// Now z is the node to be deleted, since it has either 1 or 0 child
5. par = parent[x]
6. if left[x] != NULL  //Checking if x has a left child
7.   if left[par] == x // If x is the left child
8.     left[par] = left[x]
9.   else              // If x is the right child
10.    right[par] = left[x]
11. else if right[x] != NULL //Checking if x has a right child
12.   if left[par] == x
13.     left[par] = right[x]
14.   else
15.     right[par] = right[x]
16. else if right[x] == NULL  && left[x] == NULL
17.   if left[par] == x
18.     left[par] = NULL
19.   else
20.     right[par] = NULL
21. Delete(x)
22. return root[T]

###### Code Implementation
//
//  main.cpp
//  Binary Search Tree [2]
//
//  Created by Himanshu on 16/09/21.
//

#include <iostream>
using namespace std;

struct node {
int info = 0;
struct node *left, *right, *parent;
};

typedef struct node Node;

Node* createNode (int data, Node *par) {
Node* newNode = new node();
newNode->info = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->parent = par;

return (newNode);
}

Node* insert (Node *root, int n, Node *par) {

if (root == NULL) {
root = createNode(n, par);
} else {
if (root->info > n) {
par = root;
root->left = insert (root->left, n, par);
} else {
par = root;
root->right = insert (root->right, n, par);
}
}

return root;
}

Node* search (Node *root, int n) {

if (root == NULL || root->info == n) {
return root;
} else {
if (root->info > n) {
return search (root->left, n);
} else {
return search (root->right, n);
}

}
}

Node* findMinimum (Node *root) {

while (root->left != NULL) {
root = root->left;
}

return root;
}

Node* findMaximum (Node *root) {

while (root->right != NULL) {
root = root->right;
}

return root;
}

Node* findSuccessor (Node *root) {

if (root->right != NULL) {
return findMinimum(root->right);
}

Node* y = root->parent;

while (y != NULL && root == y->right) {
root = y;
y = y->parent;
}

return y;
}

Node* deleteNode (Node *root, Node *x) {
Node *par = x->parent;

if (x->left != NULL && x->right != NULL) {
Node* z = findSuccessor(x);
x->info = z->info;
x = z;
}

par = x->parent;

if (x->left != NULL) {

if (par) {
if (par->left == x) {
par->left = x->left;
} else {
par->right = x->left;
}
} else {
root = par->left;
}

// To prevent memory leak
delete (x);
} else if (x->right != NULL) {

if (par) {
if (par->left == x) {
par->left = x->right;
} else {
par->right = x->right;
}
} else {
root = par->right;
}

// To prevent memory leak
delete (x);
} else {

if (par) {
if (par->left == x) {
par->left = NULL;
} else {
par->right = NULL;
}
} else {
root = NULL;
}

// To prevent memory leak
delete (x);
}

return root;
}

int main() {
Node *root = createNode(5, NULL);
root = insert(root, 3, NULL);
root = insert(root, 2, NULL);
root = insert(root, 4, NULL);
root = insert(root, 7, NULL);

//Searching 4 in the tree
if (search (root, 4)) {
cout<<"4 is present in the BST"<<endl;
} else {
cout<<"4 is not in the BST"<<endl;
}

//Searching parent of node 3 in the tree
Node *node = search (root, 3);
if (node->parent) {
cout<<"Parent of node 3 is "<<(node->parent->info)<<endl;
} else {
cout<<"Parent of node 3 is NULL"<<endl;
}

//Searching successor of node 2 in the tree
node = search (root, 2);
if (node) {
cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
} else {
cout<<"Successor of node 2 is NULL"<<endl;
}

//Deleting node 3 in the tree
cout<<"Deleting node 3"<<endl;
root = deleteNode(root, search (root, 3));

// Checking if node 3 exists in the tree
if (search (root, 3)) {
cout<<"3 is present in the BST"<<endl;
} else {
cout<<"3 is not in the BST"<<endl;
}

//Searching successor of node 2 in the tree
node = search (root, 2);
if (node) {
cout<<"Successor of node 2 is "<<(findSuccessor(node)->info)<<endl;
} else {
cout<<"Successor of node 2 is NULL"<<endl;
}

//Searching successor of node 4 in the tree
node = search (root, 4);
if (node) {
cout<<"Successor of node 4 is "<<(findSuccessor(node)->info)<<endl;
} else {
cout<<"Successor of node 4 is NULL"<<endl;
}

return 0;
}


Output

4 is present in the BST
Parent of node 3 is 5
Successor of node 2 is 3
Deleting node 3
3 is not in the BST
Successor of node 2 is 4
Successor of node 4 is 5

Here’s a working example: Binary Search Tree

### 10 thoughts on “Binary Search Tree in C/C++ [2]”

1. Prawdziwy przyjaciel to nie ten, kto osusza łzy twoje, Niczm jak Drapieżne lwy Tołstoje, ale ten, kto nie pozwala ci ich wylewać, innym zabrania się z Ciebie wyśmiewać E. F. Teixeira & Zeroo Cool..

2. Dzięki Ci za ten wpis jest merytoryczny i rzeczowy podnosi na duchu i inspiruje. Tak trzymaj!

3. I was checking the internet for some info since yesterday night and I ultimately found what i was looking for! This is a excellent web site by the way, although it is a little bit off place from my smart phone.

4. Wspaniały blog wiele przydatnych informacji zawartych w poszczególnych postach, Dzięki Ci za to serdeczne, zapraszam także do siebie…

5. Słowa mają ogromną moc, Ja bardzo w to wierze. Mogą inspirować, dawać motywację lub pocieszenie, a gdy go potrzeba. Czasem w jednym zdaniu jak zaklęta jest madrość, której szukamy w życiu przez bardzo długi czas. Twój blog to dosadnie urzeczywistnia!

6. Wspaniały blog wiele przydatnych informacji zawartych w poszczególnych postach, Dzięki Ci za to serdeczne, zapraszam także do siebie…

7. By aktorka odniosła sukces, powinna mieć twarz Wenus, umysł Minewry, wdzięk Terpsychory, pamięć wziętego prawnika oraz skórę z gaźnika. E. Barrymore UMS*

8. Bardzo ciekawy blog, rzeczowy i wyważony, zmusza do myślenia i refleksji. Od dzisiaj zaglądam regularnie. Pozdrowienia 🙂