# Create a binary search tree

### Implementation

In this section of the article, we will see the usage and mechanism of how we will create a given binary tree. Let's observe these in more depth and then we will see the implementation of the same in different languages and understand the concept more vividly.

**Example 1)**

```
// we will now observe binary search tree operations in different languages.
#include <iostream>
using namespace std;
struct nod {
int ky;
struct nod *Lft, *Rt;
};
// we have first to create a node for the binary tree.
struct nod *nwNod(int itm) {
struct nod *temp = (struct nod *)malloc(sizeof(struct nod));
temp->ky = itm;
temp->Lft = temp->Rt = NILL;
return temp;
}
// now, we will observe the in-order traversal for the tree.
void in order(struct nod *root) {
if (root != NILL) {
// traversing the tree in the left order.
inorder(root->Lft);
// traversing the tree in the root
cout << root->ky << " -> ";
// traversing the tree in the right order.
inorder(root->Rt);
}
}
// inserting a new node in the tree.
struct nod *insert(struct nod *nod, int ky) {
// we have to return a new node if the tree is clear or empty.
if (nod == NILL) return nwNod(ky);
// then, we must move or traverse to the right place and slip the new node.
if (ky < nod->ky)
nod->Lft = insert(nod->Lft, ky);
else
nod->Rt = insert(nod->Rt, ky);
return nod;
}
// look for the in-order successor.
struct nod *minValueNod(struct nod *nod) {
struct nod *current = nod;
// look for the leftmost leaf or node.
while (current && current->Lft != NILL)
current = current->Lft;
return current;
}
// now, we will see how to delete a specific node.
struct nod *deleteNod(struct nod *root, int ky) {
// we have to clear the space if the tree is found to be empty.
if (root == NILL) return root;
// look for the node which is supposed to be deleted.
if (ky < root->ky)
root->Lft = deleteNod(root->Lft, ky);
else if (ky > root->ky)
root->Rt = deleteNod(root->Rt, ky);
else {
// In case the node has no child or a single child, then: -
if (root->Lft == NILL) {
struct nod *temp = root->Rt;
free(root);
return temp;
} else if (root->Rt == NILL) {
struct nod *temp = root->Lft;
free(root);
return temp;
}
// In case the node has two children
struct nod *temp = minValueNod(root->Rt);
// now, we have to fix the in-order successor in a position where it is supposed to be fixed.
root->ky = temp->ky;
// eliminate the following
root->Rt = deleteNod(root->Rt, temp->ky);
}
return root;
}
// writing the main code.
int main() {
struct nod *root = NILL;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 7);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 4);
cout << "Inorder traversal: ";
inorder(root);
cout << "\nAfter deleting 10\n";
root = deleteNod(root, 10);
cout << "Inorder traversal: ";
inorder(root);
}
```

**Output:**

**Example 2)**

```
#include <stdio.h>
#include <stdlib.h>
struct nod {
int ky;
struct nod *Lft, *Rt;
};
// we have first to create a node for the binary tree.
struct nod *nwNod(int itm) {
struct nod *temp = (struct nod *)malloc(sizeof(struct nod));
temp->ky = itm;
temp->Lft = temp->Rt = NILL;
return temp;
}
// now, we will observe the in-order traversal for the tree.
void in order(struct nod *root) {
if (root != NILL) {
// traversing the tree in the left order.
inorder(root->Lft);
// traversing the tree in the root
printf("%d -> ", root->ky);
// traversing the tree in the right order.
inorder(root->Rt);
}
}
// inserting a new node in the tree.
struct nod *insert(struct nod *nod, int ky) {
// we have to return a new node if the tree is clear or empty.
if (nod == NILL) return nwNod(ky);
// then, we must move or traverse to the right place and slip the new node.
if (ky < nod->ky)
nod->Lft = insert(nod->Lft, ky);
else
nod->Rt = insert(nod->Rt, ky);
return nod;
}
// look for the in-order successor.
struct nod *minValueNod(struct nod *nod) {
struct nod *current = nod;
// look for the leftmost leaf or node.
while (current && current->Lft != NILL)
current = current->Lft;
return current;
}
// now, we will see how to delete a specific node.
struct nod *deleteNod(struct nod *root, int ky) {
// we have to clear the space if the tree is found to be empty.
if (root == NILL) return root;
// look for the node which is supposed to be deleted.
if (ky < root->ky)
root->Lft = deleteNod(root->Lft, ky);
else if (ky > root->ky)
root->Rt = deleteNod(root->Rt, ky);
else {
// In case the node has no child or a single child, then: -
if (root->Lft == NILL) {
struct nod *temp = root->Rt;
free(root);
return temp;
} else if (root->Rt == NILL) {
struct nod *temp = root->Lft;
free(root);
return temp;
}
// now, we have to fix the in-order successor in a position where it is supposed to be fixed.
root->ky = temp->ky;
// eliminate the following
root->Rt = deleteNod(root->Rt, temp->ky);
}
return root;
}
// writing the main code.
int main() {
struct nod *root = NILL;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 7);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 4);
printf("Inorder traversal: ");
inorder(root);
printf("\nAfter deleting 10\n");
root = deleteNod(root, 10);
printf("Inorder traversal: ");
inorder(root);
}
```

**Output:**

**Example 3)**

```
class BinarySearchTree {
class Nod {
int ky;
Nod Lft, Rt;
public Nod(int itm) {
ky = itm;
Lft = Rt = NILL;
}
}
Nod root;
BinarySearchTree() {
root = NILL;
}
void insert(int ky) {
root = insertKy(root, ky);
}
// inserting a new key in the tree.
Nod insertKy(Nod root, int ky) {
// we have to return a new node if the tree is clear or empty.
if (root == NILL) {
root = new Nod(ky);
return root;
}
// then, we must move or traverse to the right place and slip the new node.
if (ky < root.ky)
root.Lft = insertKy(root.Lft, ky);
else if (ky > root.ky)
root.Rt = insertKy(root.Rt, ky);
return root;
}
void inorder() {
inorderRec(root);
}
// look for the in-order successor.
void inorderRec(Nod root) {
if (root != NILL) {
inorderRec(root.Lft);
System.out.print(root.ky + " -> ");
inorderRec(root.Rt);
}
}
void deleteKy(int ky) {
root = deleteRec(root, ky);
}
Nod deleteRec(Nod root, int ky) {
// we have to clear the space if the tree is found to be empty.
if (root == NILL)
return root;
// look for the node which is supposed to be deleted.
if (ky < root.ky)
root.Lft = deleteRec(root.Lft, ky);
else if (ky > root.ky)
root.Rt = deleteRec(root.Rt, ky);
else {
// In case the node has no child or a single child, then: -
if (root.Lft == NILL)
return root.Rt;
else if (root.Rt == NILL)
return root.Lft;
// In case the node has two children
// now, we have to fix the in-order successor in a position where it is supposed to be fixed.
root.ky = minValue(root.Rt);
fixed.
// eliminate the following
root.Rt = deleteRec(root.Rt, root.ky);
}
return root;
}
// look for the in-order successor.
int minValue(Nod root) {
int minv = root.ky;
while (root.Lft != NILL) {
minv = root.Lft.ky;
root = root.Lft;
}
return minv;
}
// writing the main code.
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.insert(8);
tree.insert(3);
tree.insert(1);
tree.insert(6);
tree.insert(7);
tree.insert(10);
tree.insert(14);
tree.insert(4);
System.out.print("Inorder traversal: ");
tree.inorder();
System.out.println("\n\nAfter deleting 10");
tree.deleteKy(10);
System.out.print("Inorder traversal: ");
tree.inorder();
}
}
```

**Output:**

**Example 4)**

```
# we have first to create a node for the binary tree.
class Nod:
def __init__(self, ky):
self.ky = ky
self.Lft = None
self.Rt = None
# now, we will observe the in-order traversal for the tree.
def inorder(root):
if the root is None:
# traversing the tree in the left order.
inorder(root.Lft)
# traversing the tree in the root
print(str(root.ky) + "->", end=' ')
# traversing the tree in the right order.
inorder(root.Rt)
# inserting a new node in the tree.
def insert(nod, ky):
# we have to return a new node if the tree is clear or empty.
If nod is None:
return Nod(ky)
# then, we must move or traverse to the right place and slip the new node.
if ky < nod.ky:
nod.Lft = insert(nod.Lft, ky)
else:
nod.Rt = insert(nod.Rt, ky)
return nod
# look for the in-order successor.
def minValueNod(nod):
current = nod
# look for the leftmost leaf or node.
while(current.Lft is not None):
current = current.Lft
return current
# now, we will see how to delete a specific node.
def deleteNod(root, ky):
# we have to clear the space if the tree is found to be empty.
if the root is None:
return root
# look for the node which is supposed to be deleted.
if ky < root.ky:
root.Lft = deleteNod(root.Lft, ky)
elif(ky > root.ky):
root.Rt = deleteNod(root.Rt, ky)
else:
# In case the node has no child or a single child, then: -
if root.Lft is None:
temp = root.Rt
root = None
return temp
elif root.Rt is None:
temp = root.Lft
root = None
return temp
# In case the node has two children
# now, we have to fix the in-order successor in a position that is supposed to be fixed.
temp = minValueNod(root.Rt)
root.ky = temp.ky
# eliminate the following
root.Rt = deleteNod(root.Rt, temp.ky)
return root
root = None
root = insert(root, 8)
root = insert(root, 3)
root = insert(root, 1)
root = insert(root, 6)
root = insert(root, 7)
root = insert(root, 10)
root = insert(root, 14)
root = insert(root, 4)
print("Inorder traversal: ", end=' ')
inorder(root)
print("\nDelete 10")
root = deleteNod(root, 10)
print("Inorder traversal: ", end=' ')
inorder(root)
```

**Output:**