Threaded binary Trees !!

Traversing the binary tree is the most important operation and used in almost every application. The iterative implementation of traversing the binary tree is implemented using either stack (simulation of recursion) or using the threaded binary trees , later being the more efficient. The idea is to maintain extra information of a particular traversal which saves a lot of pushing and popping in stack implementation. This is done by maintaining extra pointer to the leaf nodes (right child in case of right-in threaded binary tree, named on the basis of same) known as thread . This is done as follows:

While adding a left child in right-in threaded binary tree

- Point the right child of the node to its parent.

While adding a right child in right -in threaded binary tree

-Point the right child of the node to the thread of the parent

The thread is detected from the normal links by using a boolean field in the node , when set to true indicates that it is actually a thread .

Here is the implementation
struct tnode *insert(struct tnode *p , int val)
{
if(p==NULL)
{
p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = val;
p->left = NULL;
p->right = NULL;
p->rthread=true;
}
else
{
struct tnode *q,*temp;
q=p;
temp=p;
while(q != NULL && q->rthread==false)
{
temp= q;
if( val >= temp->data )
q=temp->right;
else if( val < temp->data )
q=temp->left;
}
struct tnode *n;
n= (struct tnode *)malloc (sizeof(struct tnode));
n->data =val;
if( val >=temp->data )
{
if(temp->rthread)
{
struct tnode *r;
r=temp->right;
temp->right =n;
temp->rthread=false;
n->left=NULL;
n->right=r;
n->rthread=true;
}
}
else
{
temp->left = n;
n->left=NULL;
n->right=temp;
n->rthread=true;
}
}
return p;
}

A left-in-threaded binary tree  may be defined similarly, as one in which each NULL left pointer  is altered to contain a thread to that node’s inorder predecessor. An in-threaded binary tree may then be defined as a binary tree that is  both left in-threaded and right in-threaded. 

Merging two sorted linked lists !!

The problem is just like merging step in merge sort, wherein we have two sorted arrays and merge them into one. The algorithm is simple and stated as:
struct node *merge(struct node *p,struct node *q)
{
struct node *r,*s;
struct node *a=NULL;
r=p; s=q;
while(r !=NULL && s!= NULL)
{
if(r->data <= s->data)
{
a=insert(a,r->data);
r=r->link;
}
else{
a=insert(a,s->data);
s=s->link;
}
}
if(r==NULL)
while(s!=NULL)
{
a=insert(a,s->data);
s=s->link;
}
else
while(r!=NULL)
{
a=insert(a,r->data);
r=r->link;
}
return a;
}

all about binary tree !!

I recently implemented few of the operations on the binary tree. Some of the operations might match with my previous posts. I have simply posted the code. Please come up with queries if any.

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
long long test;
using namespace std;
struct tnode {
int data;
struct tnode *left;
struct tnode *right;
};
int flag=0;
struct tnode *insert(struct tnode *p , int val)
{
if(p==NULL)
{ p = (struct tnode *)malloc(sizeof(struct tnode));
p->data = val;
p->left = NULL;
p->right = NULL;
}
else
{
struct tnode *q,*temp;
q=p;
temp=p;
while(q != NULL )
{
temp= q;
if( val >= temp->data)
q=temp->right;
else
q=temp->left;
}
struct tnode *n;
n= (struct tnode *)malloc (sizeof(struct tnode));
n->data =val;
if( val >=temp->data )
temp->right =n;
else
temp->left = n;
}
return p;
}
int count1 ( struct tnode *p)
{ int c1=0;
int c2=0;
if( p != NULL){
c1=count1(p->left);
c2= count1(p->right);
return 1+c1+c2;
}
}
struct tnode *delmin(struct tnode *p)
{
struct tnode *temp=p;
while( temp->left->left != NULL)
{
temp = temp->left;
}
temp->left=NULL;
delete(temp->left);
return p;
}
struct tnode *delmax(struct tnode *p)
{
struct tnode *temp=p;
while( temp->right->right != NULL)
{
temp = temp->right;
}
temp->right=NULL;
delete(temp->right);
return p;
}
int height(struct tnode *p)
{
int h1=0;
int h2=0;
if (p == NULL)
return 0;
if(p->left)
h1= height(p->left);
if(p->right)
h2= height(p->right);
return (1+max(h1,h2));
}
bool iscomptree(struct tnode *p)
{
struct tnode *temp=p;
int l,h;
l=count1(p);
h=height(temp);
int t;
t=(int) (pow(2,((float)h))-1);
if(t == l)
return true;
else
return false;
}
struct tnode *mirror(struct tnode *p)
{
if(p == NULL)
return p ;
else
{
mirror(p->left);
mirror(p->right);
struct tnode *temp;
temp=p->left;
p->left=p->right;
p->right=temp;
}
return p;
}
bool identical(struct tnode* a, struct tnode* b)
{
if (a==NULL && b==NULL){return(true);}
else if (a!=NULL && b!=NULL)
{
return(a->data == b->data &&
identical(a->left, b->left) &&
identical(a->right, b->right));
}
else return(false);
}
int check( struct tnode *p)
{ int h1,h2,sum=0;
if(p != NULL)
{
if(p->left && ! (p->right) || p->right && !(p->left))
{
flag=1;
return flag;
}
else{
if(flag != 1)
{
flag= check(p->left);
flag=check(p->right);
}
}
}
return flag;
}
int add ( struct tnode *p)
{ int sum1=0, sum2=0 ;
if( p != NULL){
sum1=add(p->left);
sum2=add(p->right);
return sum1+sum2+p->data;
}
}
void inorder ( struct tnode *p)
{
if( p != NULL){
inorder(p->left);
printf("%d\t",p->data);
inorder(p->right);
}
}
void preorder ( struct tnode *p)
{
if( p != NULL){
printf("%d\t",p->data);
preorder(p->left);
preorder(p->right);
}
}
void postorder ( struct tnode *p)
{
if( p != NULL){
postorder(p->left);
postorder(p->right);
printf("%d\t",p->data);
}
}
main()
{
struct tnode *root=NULL;
root=insert(root,16);
root=insert(root,14);
root=insert(root,20);
root=insert(root,12);
root=insert(root,15);
root=insert(root,18);
root=insert(root,22);
printf("Inorder traversal of the tree\n");
inorder(root);
cout<<endl;
printf("Preorder traversal of the tree\n");
preorder(root);
cout<<endl;
printf("Postorder traversal of the tree\n");
postorder(root);
cout<<endl;
printf("Height of the binary tree : ");
cout<<height(root)-1;
cout<<endl;
printf("Strictly binary tree[=0]: ");
cout<<check(root);
cout<<endl;
printf("Complete binary tree[=1]: ");
cout<<iscomptree(root);
cout<<endl;
struct tnode *r;
cout<<endl;
root=delmin(root);
inorder(root);
root=delmax(root);
cout<<endl;
inorder(root);
}

Level order traversal!

For the level order of the binary tree:

1- start from the root, display it

2-put the left child and then right child in a queue

3-again consider the first element of the queue as root and repeat the procedure till the whole tree is traversed.

here is the C code :

void levelorder(struct tnode *p)
{
struct tnode *queue[100]={(struct tnode*) 0};
int size=0;
int qptr=0;
while(p)
{
printf("%d\t",p->data);
if(p->left)
{
queue[size++]=p->left;
}
if(p->right)
{
queue[size++]=p->right;
}
p=queue[qptr++];
}
}

Height of the binary tree!

Find the height of the given binary tree.

Its simple , isn’t it?

1- traverse all left nodes recursively say, h1

2-traverse all right nodes recursively say,h2

height is max(h1,h2)

It can be coded as:
int height(struct tnode *p)
{
struct tnode *temp=p;
int h1=0,h2=0;
if(p==NULL)return(0);
if(p->left){h1=height(p->left);}
if(p->right){h2=height(p->right);}
return(max(h1,h2)+1);
}

The number of the nodes in the binary tree can be found as:

int number(struct tnode *p)
{
if(p == NULL)
return 0;
else
return (number(p->left)+number(p->right)+1);
}

Insert in sorted fashion!!

Inserting nodes into a linked list in a sorted fashion

//linked list in sorted fashion
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
struct node {
int data;
struct node *link;
};
struct node *insert(struct node *p, int val)
{
if(p==NULL)
{
p=(struct node*)malloc(sizeof(struct node));
p->data=val;
p->link=NULL;
}
else{
struct node *temp=p;
while( temp->link !=NULL && temp->link->data < val)
{
temp=temp->link;
}
struct node *y;
y=(struct node*) malloc(sizeof(struct node*));
y->data=val;
y->link=temp->link;
temp->link=y;
}
return p;
}
void disply(struct node *p)
{
if(p==NULL)
{
printf("The list is empty\n");
}
while(p != NULL)
{
printf("%d\t",p->data);
p=p->link;
}
printf("\n");
}
main()
{
struct node *root=NULL;
root=insert(root,1);
root=insert(root,234);
root=insert(root,34);
root=insert(root,1333);
disply(root);
system("pause");
}

nth node from last of the linked list!

The idea is quite simple, take two pointers P1,P2 and point them to the first node.

1- Increment P1 till the nth node from start comes .

2- Now, start the second pointer P2 and keep on incrementing it till the first pointer P1 reaches the end of the Linked list.

int nodelast( struct node *p , int n)
{
struct node *p1,*p2;
p1=p2=p;
int c=0;
while( c < n)
{
if(p1 == NULL)
{
printf("there are not enough elements in the list");
exit(0);
}
p1=p1->link;
c++;
}
while(p1 != NULL)
{
p2=p2->link;
p1=p1->link;
}
return p2->data;
}

Compare two linked lists !

Comparing two lists means , return true if they are exactly same otherwise return false.

I have done it recursively.

bool compare( struct node *p1, struct node *p2)
{
if( p1==NULL && p2==NULL)
return true;
else if( p1==NULL || p2==NULL)
return false;
else if(p1->data !=p2->data)
return false;
else
compare(p1->link,p2->link) ;
return true;
}

Middle of the linked list!!

Find the middle element of the linked list just in one traversal of the list.

1- Take two pointers P1 and P2 , both pointed to the first element.

2- Increment P1 by 1 and P2 by two.

3-Whenever P2 reaches to the end, P1 will be at the middle of the list, just return P1->data.

But I think we have traversed the list for 1.5 times because P1 and P2 both traversed few nodes. Is it cheating? Could not find any better solution.

int getmiddle(struct node *p)
{
int mid;
struct node *p1,*p2;
p1=p2=p;
while(p2->link != NULL && p2->link->link != NULL)
{
p1=p1->link;
p2=p2->link->link;
}
return p1->data;
}

It works fine as far as number of nodes in the list are odd. What is the middle element in case of even numbered linked list. Should we return two elements?

Sorted Linear Linked list!!

There can be various methods to sort the linear linked list. Few of them are discussed here.

1- I can compare the data value of the list and swap them if needed ( just like bubble sort)

struct node *sort(struct node *p)
{
int it;
struct node *temp1,*temp2;
temp1=p;
while(temp1->link != NULL)
{
temp2=temp1;
while(temp2 != NULL)
{
if(temp1->data > temp2->data)
{
it=temp1->data;
temp1->data= temp2->data;
temp2->data=it;
}
temp2=temp2->link;
}
temp1=temp1->link;
}
return p;
}