Tag Archives: binary tree

C program to mirror binary tree

July 27, 2013 admin

C function to mirror binary tree.

C Function implementation :

/* C Function to Mirror Binary Tree */

void mirrorbst(struct Tnode *Troot){
    struct Tnode *tmp;
    if(Troot==NULL) return;
    mirrorbst(Troot->left);
    mirrorbst(Troot->right);
    tmp=Troot->left;
    Troot->left=Troot->right;
    Troot->right=tmp;
}

/* C Function to Mirror Binary Tree */

void mirrorbst(struct Tnode *Troot){

struct Tnode *tmp;

if(Troot==NULL) return;

mirrorbst(Troot->left);

mirrorbst(Troot->right);

tmp=Troot->left;

Troot->left=Troot->right;

Troot->right=tmp;

}

Complete C Code implementation

/* Binary Search tree code by condingstreet.com */
#include<stdio.h>
#include<stdlib.h>
struct Tnode {
    int val;
    struct Tnode *left,*right;
};
int create_node(int val,struct Tnode **node){
    struct Tnode *tmp;
    tmp=malloc(sizeof(struct Tnode));
    if(tmp==NULL) return 0;
    tmp->val=val;
    tmp->left=NULL;
    tmp->right=NULL;
    (*node)=tmp;
    return 1;
}
void insert_node(struct Tnode **Troot,struct Tnode **node){
    struct Tnode *parent,*tmp;
    int val;
    if((*node)==NULL) return;
    if((*Troot)==NULL){
    (*Troot)=(*node);
    return;
    }
    tmp=(*Troot);
    val=(*node)->val;
    while(tmp!=NULL){
    parent=tmp;
    if(val<tmp->val) tmp=tmp->left;
    else tmp=tmp->right;
    }
    if(val<parent->val){
    parent->left=(*node);
    }
    else parent->right=(*node);
    return;
}
void inorder(struct Tnode *node){
if(node!=NULL){
    inorder(node->left);
    printf(" %d ",node->val);
    inorder(node->right);
    }
}
/* C Function to Mirror Binary Tree */

void mirrorbst(struct Tnode *Troot){
    struct Tnode *tmp;
    if(Troot==NULL) return;
    mirrorbst(Troot->left);
    mirrorbst(Troot->right);
    tmp=Troot->left;
    Troot->left=Troot->right;
    Troot->right=tmp;
}

int main(){
struct Tnode *root=NULL,*node;
int key,ival;
do{
printf("\n[1] Insert value");
printf("\n[2] Print inorder ");
printf("\n[3] Mirror Bst ");
printf("\n[4] Exit");
printf("\nEnter the input key : ");
scanf("%d",&key);
switch(key){
case 1:
    printf("\n Enter the value to be inserted :");
    scanf("%d",&ival);
    if(create_node(ival,&node))
        insert_node(&root,&node);
    else printf("\n Memory is Full !! ");
break;
case 2:
  inorder(root);
break;
case 3:
    mirrorbst(root);
break;
case 4:
break;
default:
printf("\t Enter the Correct key !!!!! ");
break;
}
}while(key!=4);

printf("\n Thank you for using codingstreet.com 's datastructure solution ");
return 0;
}

/* Binary Search tree code by condingstreet.com */

#include<stdio.h>

#include<stdlib.h>

struct Tnode {

int val;

struct Tnode *left,*right;

};

int create_node(int val,struct Tnode **node){

struct Tnode *tmp;

tmp=malloc(sizeof(struct Tnode));

if(tmp==NULL) return 0;

tmp->val=val;

tmp->left=NULL;

tmp->right=NULL;

(*node)=tmp;

return 1;

}

void insert_node(struct Tnode **Troot,struct Tnode **node){

struct Tnode *parent,*tmp;

int val;

if((*node)==NULL) return;

if((*Troot)==NULL){

(*Troot)=(*node);

return;

}

tmp=(*Troot);

val=(*node)->val;

while(tmp!=NULL){

parent=tmp;

if(val<tmp->val) tmp=tmp->left;

else tmp=tmp->right;

}

if(val<parent->val){

parent->left=(*node);

}

else parent->right=(*node);

return;

}

void inorder(struct Tnode *node){

if(node!=NULL){

inorder(node->left);

printf(" %d ",node->val);

inorder(node->right);

}

/* C Function to Mirror Binary Tree */

void mirrorbst(struct Tnode *Troot){

struct Tnode *tmp;

if(Troot==NULL) return;

mirrorbst(Troot->left);

mirrorbst(Troot->right);

tmp=Troot->left;

Troot->left=Troot->right;

Troot->right=tmp;

}

int main(){

struct Tnode *root=NULL,*node;

int key,ival;

do{

printf("\n[1] Insert value");

printf("\n[2] Print inorder ");

printf("\n[3] Mirror Bst ");

printf("\n[4] Exit");

printf("\nEnter the input key : ");

scanf("%d",&key);

switch(key){

case 1:

printf("\n Enter the value to be inserted :");

scanf("%d",&ival);

if(create_node(ival,&node))

insert_node(&root,&node);

else printf("\n Memory is Full !! ");

break;

case 2:

inorder(root);

break;

case 3:

mirrorbst(root);

break;

case 4:

break;

default:

printf("\t Enter the Correct key !!!!! ");

break;

}

}while(key!=4);

printf("\n Thank you for using codingstreet.com 's datastructure solution ");

return 0;

}

Print Ancestor of given node value in binary tree

July 24, 2013 admin

Print Ancestor of given node value in binary tree.

For Given Binary Search tree find out the ancestor of a given node value .

Binary Search Tree , 8 is root node ,left branch has nodes whose value are less than 8 and right branch has nodes whose values are greater than 8 — Binary Search Tree

Node Value O/P

4 8 3 6

13 8 10 14

Recursive function to print ancestor values for given binary search tree.

int printances(struct Tnode *Troot1,int nodeval){
    if(Troot1==NULL) return 0;
    if(nodeval==Troot1->val) return 1;
    if(printances(Troot1->left,nodeval)||printances(Troot1->right,nodeval))
    {    printf(" %d ",Troot1->val);
         return 1;
    }
   return 0;
}

int printances(struct Tnode *Troot1,int nodeval){

if(Troot1==NULL) return 0;

if(nodeval==Troot1->val) return 1;

if(printances(Troot1->left,nodeval)||printances(Troot1->right,nodeval))

{ printf(" %d ",Troot1->val);

return 1;

}

return 0;

}

Complete code with binary search tree implementation and ancestor printing function.

/* Binary Search tree code by condingstreet.com */
#include<stdio.h>
#include<stdlib.h>
struct Tnode {
    int val;
    struct Tnode *left,*right;
};
int create_node(int val,struct Tnode **node){
    struct Tnode *tmp;
    tmp=malloc(sizeof(struct Tnode));
    if(tmp==NULL) return 0;
    tmp->val=val;
    tmp->left=NULL;
    tmp->right=NULL;
    (*node)=tmp;
    return 1;
}
void insert_node(struct Tnode **Troot,struct Tnode **node){
    struct Tnode *parent,*tmp;
    int val;
    if((*node)==NULL) return;
    if((*Troot)==NULL){
    (*Troot)=(*node);
    return;
    }
    tmp=(*Troot);
    val=(*node)->val;
    while(tmp!=NULL){
    parent=tmp;
    if(val<tmp->val) tmp=tmp->left;
    else tmp=tmp->right;
    }
    if(val<parent->val){
    parent->left=(*node);
    }
    else parent->right=(*node);
    return;
}
int printances(struct Tnode *Troot1,int nodeval){
    if(Troot1==NULL) return 0;
    if(nodeval==Troot1->val) return 1;
    if(printances(Troot1->left,nodeval)||printances(Troot1->right,nodeval))
        printf(" %d ",Troot1->val);
}
int main(){
struct Tnode *root=NULL,*node;
int key,ival;
do{
printf("\n[1] Insert value");
printf("\n[2] Print Ancestors ");
printf("\n[3] Exit ");
printf("\nEnter the input key : ");
scanf("%d",&key);
switch(key){
case 1:
    printf("\n Enter the value to be inserted :");
    scanf("%d",&ival);
    if(create_node(ival,&node))
        insert_node(&root,&node);
    else printf("\n Memory is Full !! ");
break;
case 2:
    printf("\n Enter the value whose ancestore to be calculated :");
    scanf("%d",&ival);
    printances(root,ival);
break;
case 3:
break;
default:
printf("\t Enter the Correct key !!!!! ");
break;
}
}while(key!=3);

printf("\n Thank you for using codingstreet.com 's datastructure solution ");
return 0;
}

/* Binary Search tree code by condingstreet.com */

#include<stdio.h>

#include<stdlib.h>

struct Tnode {

int val;

struct Tnode *left,*right;

};

int create_node(int val,struct Tnode **node){

struct Tnode *tmp;

tmp=malloc(sizeof(struct Tnode));

if(tmp==NULL) return 0;

tmp->val=val;

tmp->left=NULL;

tmp->right=NULL;

(*node)=tmp;

return 1;

}

void insert_node(struct Tnode **Troot,struct Tnode **node){

struct Tnode *parent,*tmp;

int val;

if((*node)==NULL) return;

if((*Troot)==NULL){

(*Troot)=(*node);

return;

}

tmp=(*Troot);

val=(*node)->val;

while(tmp!=NULL){

parent=tmp;

if(val<tmp->val) tmp=tmp->left;

else tmp=tmp->right;

}

if(val<parent->val){

parent->left=(*node);

}

else parent->right=(*node);

return;

}

int printances(struct Tnode *Troot1,int nodeval){

if(Troot1==NULL) return 0;

if(nodeval==Troot1->val) return 1;

if(printances(Troot1->left,nodeval)||printances(Troot1->right,nodeval))

printf(" %d ",Troot1->val);

}

int main(){

struct Tnode *root=NULL,*node;

int key,ival;

do{

printf("\n[1] Insert value");

printf("\n[2] Print Ancestors ");

printf("\n[3] Exit ");

printf("\nEnter the input key : ");

scanf("%d",&key);

switch(key){

case 1:

printf("\n Enter the value to be inserted :");

scanf("%d",&ival);

if(create_node(ival,&node))

insert_node(&root,&node);

else printf("\n Memory is Full !! ");

break;

case 2:

printf("\n Enter the value whose ancestore to be calculated :");

scanf("%d",&ival);

printances(root,ival);

break;

case 3:

break;

default:

printf("\t Enter the Correct key !!!!! ");

break;

}

}while(key!=3);

printf("\n Thank you for using codingstreet.com 's datastructure solution ");

return 0;

}

binary search tree, Tree

Binary Tree implementation with print all paths

July 21, 2013 admin

Binary Tree implementation code with print all paths in Binary tree Code in C.

/* Binary Search tree code by condingstreet.com */
#include<stdio.h>
#include<stdlib.h>
struct Tnode {
    int val;
    struct Tnode *left,*right;
};
struct snode{
    struct Tnode *node;
    struct snode *next;
};
int create_node(int val,struct Tnode **node){
    struct Tnode *tmp;
    tmp=malloc(sizeof(struct Tnode));
    if(tmp==NULL) return 0;
    tmp->val=val;
    tmp->left=NULL;
    tmp->right=NULL;
    (*node)=tmp;
    return 1;
}
void insert_node(struct Tnode **Troot,struct Tnode **node){
    struct Tnode *parent,*tmp;
    int val;
    if((*node)==NULL) return;
    if((*Troot)==NULL){
    (*Troot)=(*node);
    return;
    }
    tmp=(*Troot);
    val=(*node)->val;
    while(tmp!=NULL){
    parent=tmp;
    if(val<tmp->val) tmp=tmp->left;
    else tmp=tmp->right;
    }
    if(val<parent->val){
    parent->left=(*node);
    }
    else parent->right=(*node);
    return;
}
void push_sstack(struct snode **stack,struct Tnode *node){
    struct snode *stop,*tmp;
    stop=*stack;
    if(stop==NULL){
    tmp=malloc(sizeof(struct snode));
    tmp->node=node;
    tmp->next=NULL;
    (*stack)=tmp;
    }
    else {
    tmp=malloc(sizeof(struct snode));
    if(tmp!=NULL){
    tmp->node=node;
    tmp->next=stop;
    (*stack)=tmp;}
    else     printf(" \n Memory is Full Can't insert value\n ");
    }
}
struct Tnode *pop_sstack(struct snode **stack){
    if((*stack)!=NULL)
    {
    struct Tnode *rval;
    struct snode *tmp,*stop;
    stop=(*stack);
    tmp=stop;
    rval=tmp->node;
    stop=stop->next;
    *stack=stop;
    tmp->next=NULL;
    free(tmp);
    return rval;
    }
    return NULL;
}
int is_stack_empty(struct snode **stack){
    if((*stack)==NULL) return 1;
    else return 0;
}
void printpaths(struct Tnode *root){
    int path[800];
    printpathrec(root,path,0);
}
void printarray(int path[],int pathlen){
int i;
    for(i=0;i<pathlen;i++)
        printf(" %d ",path[i]);
printf("\n");
}
void printpathrec(struct Tnode *root, int path[],int pathlen){
    if(root==NULL) return;
    path[pathlen]=root->val;
    pathlen++;
    if(root->left==NULL && root->right==NULL){
        printarray(path,pathlen);
    }
    else {
        printpathrec(root->left,path,pathlen);
        printpathrec(root->right,path,pathlen);
    }
}
void inorder_iterative(struct Tnode **Troot )
{
    if((*Troot)==NULL) return;
    struct snode *s1;
    struct Tnode *curnode=(*Troot);
    while(!is_stack_empty(&s1) || curnode!=NULL)
    {
        if(curnode!=NULL) {
                push_sstack(&s1,curnode);
                curnode=curnode->left;
        }
        else {
            curnode=pop_sstack(&s1);
            printf(" %d ",curnode->val);
            curnode=curnode->right;
        }

    }
}

int main(){
struct Tnode *root=NULL,*node;
int key,ival,*sum,ssum=0;
sum=&ssum;
do{
printf("\n[1] Insert value");
printf("\n[2] Print Tree (inorder) ");
printf("\n[3] Print paths");
printf("\n[4] Exit ");
printf("\nEnter the input key : ");
scanf("%d",&key);
switch(key){
case 1:
    printf("\n Enter the value to be inserted :");
    scanf("%d",&ival);
    if(create_node(ival,&node))
        insert_node(&root,&node);
    else printf("\n Memory is Full !! ");
break;
case 2:
printf("\n Tree contents are :\n");
    inorder_iterative(&root);
break;
case 3:
    printpaths(root);
break;
case 4:
break;
default:
printf("\t Enter the Correct key !!!!! ");
break;
}
}while(key!=4);

printf("\n Thank you for using codingstreet.com 's datastructure solution ");
return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

/* Binary Search tree code by condingstreet.com */

#include<stdio.h>

#include<stdlib.h>

struct Tnode {

int val;

struct Tnode *left,*right;

};

struct snode{

struct Tnode *node;

struct snode *next;

};

int create_node(int val,struct Tnode **node){

struct Tnode *tmp;

tmp=malloc(sizeof(struct Tnode));

if(tmp==NULL) return 0;

tmp->val=val;

tmp->left=NULL;

tmp->right=NULL;

(*node)=tmp;

return 1;

}

void insert_node(struct Tnode **Troot,struct Tnode **node){

struct Tnode *parent,*tmp;

int val;

if((*node)==NULL) return;

if((*Troot)==NULL){

(*Troot)=(*node);

return;

}

tmp=(*Troot);

val=(*node)->val;

while(tmp!=NULL){

parent=tmp;

if(val<tmp->val) tmp=tmp->left;

else tmp=tmp->right;

}

if(val<parent->val){

parent->left=(*node);

}

else parent->right=(*node);

return;

}

void push_sstack(struct snode **stack,struct Tnode *node){

struct snode *stop,*tmp;

stop=*stack;

if(stop==NULL){

tmp=malloc(sizeof(struct snode));

tmp->node=node;

tmp->next=NULL;

(*stack)=tmp;

}

else {

tmp=malloc(sizeof(struct snode));

if(tmp!=NULL){

tmp->node=node;

tmp->next=stop;

(*stack)=tmp;}

else printf(" \n Memory is Full Can't insert value\n ");

}

struct Tnode *pop_sstack(struct snode **stack){

if((*stack)!=NULL)

{

struct Tnode *rval;

struct snode *tmp,*stop;

stop=(*stack);

tmp=stop;

rval=tmp->node;

stop=stop->next;

*stack=stop;

tmp->next=NULL;

free(tmp);

return rval;

}

return NULL;

}

int is_stack_empty(struct snode **stack){

if((*stack)==NULL) return 1;

else return 0;

}

void printpaths(struct Tnode *root){

int path[800];

printpathrec(root,path,0);

}

void printarray(int path[],int pathlen){

int i;

for(i=0;i<pathlen;i++)

printf(" %d ",path[i]);

printf("\n");

}

void printpathrec(struct Tnode *root, int path[],int pathlen){

if(root==NULL) return;

path[pathlen]=root->val;

pathlen++;

if(root->left==NULL && root->right==NULL){

printarray(path,pathlen);

}

else {

printpathrec(root->left,path,pathlen);

printpathrec(root->right,path,pathlen);

}

void inorder_iterative(struct Tnode **Troot )

{

if((*Troot)==NULL) return;

struct snode *s1;

struct Tnode *curnode=(*Troot);

while(!is_stack_empty(&s1) || curnode!=NULL)

{

if(curnode!=NULL) {

push_sstack(&s1,curnode);

curnode=curnode->left;

}

else {

curnode=pop_sstack(&s1);

printf(" %d ",curnode->val);

curnode=curnode->right;

}

int main(){

struct Tnode *root=NULL,*node;

int key,ival,*sum,ssum=0;

sum=&ssum;

do{

printf("\n[1] Insert value");

printf("\n[2] Print Tree (inorder) ");

printf("\n[3] Print paths");

printf("\n[4] Exit ");

printf("\nEnter the input key : ");

scanf("%d",&key);

switch(key){

case 1:

printf("\n Enter the value to be inserted :");

scanf("%d",&ival);

if(create_node(ival,&node))

insert_node(&root,&node);

else printf("\n Memory is Full !! ");

break;

case 2:

printf("\n Tree contents are :\n");

inorder_iterative(&root);

break;

case 3:

printpaths(root);

break;

case 4:

break;

default:

printf("\t Enter the Correct key !!!!! ");

break;

}

}while(key!=4);

printf("\n Thank you for using codingstreet.com 's datastructure solution ");

return 0;

}

binary search tree, Tree

Print all paths in Binary Tree

July 21, 2013 admin

C function to print all paths in binary tree from root to leaf.

For a given binary tree o/p should be :

Print all paths o/p :

8 3 1

8 3 6 4

8 3 6 7

8 10 14 13

void printpaths(struct Tnode *root){
    int path[800];
    printpathrec(root,path,0);
}
void printarray(int path[],int pathlen){
int i;
    for(i=0;i<pathlen;i++)
        printf(" %d ",path[i]);
printf("\n");
}
void printpathrec(struct Tnode *root, int path[],int pathlen){
    if(root==NULL) return;
    path[pathlen]=root->val;
    pathlen++;
    if(root->left==NULL && root->right==NULL){
        printarray(path,pathlen);
    }
    else {
        printpathrec(root->left,path,pathlen);
        printpathrec(root->right,path,pathlen);
    }
}

void printpaths(struct Tnode *root){

int path[800];

printpathrec(root,path,0);

}

void printarray(int path[],int pathlen){

int i;

for(i=0;i<pathlen;i++)

printf(" %d ",path[i]);

printf("\n");

}

void printpathrec(struct Tnode *root, int path[],int pathlen){

if(root==NULL) return;

path[pathlen]=root->val;

pathlen++;

if(root->left==NULL && root->right==NULL){

printarray(path,pathlen);

}

else {

printpathrec(root->left,path,pathlen);

printpathrec(root->right,path,pathlen);

}

==> Click Here to Get Complete C Code of Binary Search Tree implementation

==> Click here to Get Code for all Path Print and Binary Tree implementation

References : http://cslibrary.stanford.edu/110/BinaryTrees.html

Codingstreet

Tag Archives: binary tree

C program to mirror binary tree

Print Ancestor of given node value in binary tree

Binary Tree implementation with print all paths

Print all paths in Binary Tree

A place to brush your coding skills