# 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: 