Question

Binary Tree

Develop algorithms for performing various operations of binary tree like insertion and deletion of elements, finding an element in the binary tree. Analyse time and space complexity of the designed algorithm Write C++ program to implement binary tree

Answer 1

Insertion

#include <iostream>

#include <queue>

using namespace std;

//Create a struct for key and left and right of the node

struct nod {

int key;

struct nod* lt, *rt;

};

//function to create a new nod of tree

struct nod* newnod(int key)

{

struct nod* tmp = new nod;

tmp->key = key;

tmp->lt = tmp->rt = NULL;

return tmp;

};

//Inorder traversal of a binary tree

void inorder(struct nod* tmp)

{

if (!tmp)

return;

inorder(tmp->lt);

cout << tmp->key << " ";

inorder(tmp->rt);

}

//function to insert element in binary tree

void insert(struct nod* tmp, int key)

{

queue<struct nod*> q;

q.push(tmp);

while (!q.empty()) {

struct nod* tmp = q.front();

q.pop();

if (!tmp->lt) {

tmp->lt = newnod(key);

break;

} else

q.push(tmp->lt);

if (!tmp->rt) {

tmp->rt = newnod(key);

break;

} else

q.push(tmp->rt);

}

}

int main()

{

struct nod* root = newnod(20);

root->lt = newnod(1);

root->lt->lt = newnod(6);

root->rt = newnod(5);

root->rt->lt = newnod(4);

root->rt->rt = newnod(3);

cout << "Inorder traversal before insertion:";

inorder(root);

int key = 13;

insert(root, key);

cout << endl;

cout << "Inorder traversal after insertion:";

inorder(root);

return 0;

}

Deletion

#include <bits/stdc++.h>
using namespace std;

/* A binary tree nod has k, pointer to lt
child and a pointer to rt child */
struct nod {
int k;
struct nod *lt, *rt;
};

//create a new nod of tree
struct nod* newnod(int k)
{
struct nod* tmp = new nod;
tmp->k = k;
tmp->lt = tmp->rt = NULL;
return tmp;
};

//inorder traversal
void in(struct nod* tmp)
{
if (!tmp)
return;
in(tmp->lt);
cout << tmp->k << " ";
in(tmp->rt);
}

// delete the given last node
void last(struct nod* root,
struct nod* d_nod)
{
queue<struct nod*> q;
q.push(root);

//level order traversal until last nod
struct nod* tmp;
while (!q.empty()) {
tmp = q.front();
q.pop();
if (tmp == d_nod) {
tmp = NULL;
delete (d_nod);
return;
}
if (tmp->rt) {
if (tmp->rt == d_nod) {
tmp->rt = NULL;
delete (d_nod);
return;
}
else
q.push(tmp->rt);
}

if (tmp->lt) {
if (tmp->lt == d_nod) {
tmp->lt = NULL;
delete (d_nod);
return;
}
else
q.push(tmp->lt);
}
}
}

// delete element in tree
nod* del(struct nod* root, int k)
{
if (root == NULL)
return NULL;

if (root->lt == NULL && root->rt == NULL) {
if (root->k == k)
return NULL;
else
return root;
}

queue<struct nod*> q;
q.push(root);

struct nod* tmp;
struct nod* k_nod = NULL;
while (!q.empty()) {
tmp = q.front();
q.pop();

if (tmp->k == k)
k_nod = tmp;

if (tmp->lt)
q.push(tmp->lt);

if (tmp->rt)
q.push(tmp->rt);
}

if (k_nod != NULL) {
int x = tmp->k;
last(root, tmp);
k_nod->k = x;
}
return root;
}

int main()
{
struct nod* root = newnod(11);
root->lt = newnod(15);
root->lt->lt = newnod(8);
root->lt->rt = newnod(16);
root->rt = newnod(19);
root->rt->lt = newnod(12);
root->rt->rt = newnod(1);

cout << "in traversal before del : ";
in(root);

int k = 19;
root = del(root, k);

cout << endl;
cout << "in traversal after del : ";
in(root);

return 0;
}

Search

#include <iostream>
using namespace std;

struct nod{
int data;
struct nod* lt, *rt;
nod(int data)
{
this->data = data;
lt= rt = NULL;
}
};

// Function to traverse the tree in preorder
// and check if the given nodxists in it
bool Exists(struct nod* nod, int key)
{
if (nod== NULL)
return false;

if (nod->data == key)
return true;

bool r1 = Exists(nod->lt, key);

bool r2 = Exists(nod->rt, key);

return r1 || r2;
}

int main()
{
struct nod* root = new nod(0);
root->lt= new nod(1);
root->lt->lt= new nod(3);
root->lt->lt->lt= new nod(7);
root->lt->rt = new nod(4);
root->lt->rt->lt= new nod(8);
root->lt->rt->rt = new nod(9);
root->rt = new nod(2);
root->rt->lt= new nod(5);
root->rt->rt = new nod(6);

int key = 4;

if (Exists(root, key))
cout << "YES";
else
cout << "NO";

return 0;
}

Analysis

Searching: for searching a element we have to traverse to all elements.Therfore searching in binary tree have a complexity of O(n)
Insertion: for insertion a element we have to traverse to all elements.Therfore insertion in binary tree have a complexity of O(n)
Deletion:for searching a elemet we have to traverse to all elements.Therfore searching in binary tree have a complexity of O(n)