```
```tnode *insert(tnode *p,int val);

void preorder(tnode *p);

void inorder(tnode *p);

void postorder(tnode *p);

void levelorder(tnode *p);

int height(tnode *p);

int countnode(tnode *p);

int internal(tnode *p);

int leaf(tnode *p);

tnode *delmin(tnode *p);

tnode *delmax(tnode *p);

int sum(tnode *p);

void complete(tnode *p);

int strict(tnode *p);

tnode *mirror(tnode *p);

int search( tnode *p, int val);

void display(tnode *p,int val);

bool identical(tnode *p,tnode *q);

//tnode *del(tnode *p,int num);

void printPathsRecur(struct tnode* node, int path[], int pathLen);

void printArray(int ints[], int len);

/*

Given a binary tree, print out all of its root-to-leaf

paths, one per line. Uses a recursive helper to do the work.

*/

void printPaths(struct tnode* node) {

int path[1000];

printPathsRecur(node, path, 0);

}

/*

Recursive helper function -- given a node, and an array containing

the path from the root node up to but not including this node,

print out all the root-leaf paths.

*/

void printPathsRecur(struct tnode* node, int path[], int pathLen) {

if (node==NULL) return;

// append this node to the path array

path[pathLen] = node->data;

pathLen++;

// it's a leaf, so print the path that led to here

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

printArray(path, pathLen);

}

else {

// otherwise try both subtrees

printPathsRecur(node->left, path, pathLen);

printPathsRecur(node->right, path, pathLen);

}

}

// Utility that prints out an array on a line.

void printArray(int ints[], int len) {

int i;

for (i=0; ileft);

doubleTree(node->right);

// duplicate this node to its left

oldLeft = node->left;

tnode *temp= new tnode;

temp->data=node->data; //Node(node->data);

temp->left=NULL;

temp->right=NULL;

node->left=temp;

node->left->left = oldLeft;

return node;

}

int countTrees(int numKeys) {

if (numKeys <=1) {

return(1);

}

else {

// there will be one value at the root, with whatever remains

// on the left and right each forming their own subtrees.

// Iterate through all the values that could be the root...

int sum = 0;

int left, right, root;

for (root=1; root<=numKeys; root++) {

left = countTrees(root - 1);

right = countTrees(numKeys - root);

// number of possible trees with this root == left*right

sum += left*right;

}

return(sum);

}

}

int main()

{

struct tnode *p=NULL;

p=insert(p,10);

p=insert(p,101);

p=insert(p,13);

p=insert(p,15);

p=insert(p,67);

p=insert(p,9);

p=insert(p,4);

p=insert(p,34);

cout<<"\n inorder traversal is :\n";

inorder(p);

cout<<"\n\n level order traversal is :\n";

levelorder(p);

cout<<"\n\n height of bst is :"<<height(p)-1;

cout<<"\n\n total node in bst is :"<<countnode(p);

cout<<"\n\n total no. of internal node in bst is :"<<internal(p);

cout<<"\n\n total no. of leaf in bst is :"<<leaf(p);

tnode *q;

q=insert(p,5);

cout<<endl<<endl;

inorder(q);

cout<<"\n\n sum of node is :"<<sum(q);

complete(p);

strict(p);

if(identical(p,p)==1)

cout<<"\n tree is identical ";

else

cout<<"\n tree is not identical ";

display(p,34);

display(p,99);

cout<<"\n\n after deletion of minimum :";

p=delmin(p);

inorder(p);

cout<<"\n\n after deletion of maxmum :";

p=delmax(p);

inorder(p);

cout<<"\n\n mirror is ";

mirror(p);

inorder(p);

cout<<"\n print paths is from root to leaf ... \n";

printPaths(p);

cout<<"\n the no. of tree which can be made from 5 no. is :"<<countTrees(5)<<endl;

doubleTree(p);

cout<<endl<data=val;

p->left=NULL;

p->right=NULL;

}

else

{

tnode *temp,*q;

q=p;

while(q!=NULL)

{

temp=q;

if(temp->dataright;

else

q=temp->left;

}

tnode *n=new tnode;

n->data=val;

n->left=NULL;

n->right=NULL;

if(val>=temp->data)

temp->right=n;

else

temp->left=n;

}

return p;

}

*/

//insert by recurssion

tnode *insert(tnode *p,int val)

{

if(p==NULL)

{

p=new tnode;

p->data=val;

p->left=NULL;

p->right=NULL;

}

else

{

if(val

data)

p->left=insert(p->left,val);

else

p->right=insert(p->right,val);

}

return p;

}

void preorder(tnode *p)

{

if(p!=NULL)

{

cout<

data<left);

preorder(p->right);

}

}

void inorder(tnode *p)

{

if(p!=NULL)

{

inorder(p->left);

cout<

data<right);

}

}

void postorder(tnode *p)

{

if(p!=NULL)

{

postorder(p->left);

postorder(p->right);

cout<

data<<" ";

}

}

void levelorder(tnode *p)

{

tnode *queue[100]= {(tnode *)0} ;

int size=0;

int q=0;

while(p!=NULL)

{

cout<

data<left)

queue[size++]=p->left;

if(p->right)

queue[size++]=p->right;

p=queue[q++];

}

}

int height(tnode *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);

int max;

if(h1>h2)

max=h1;

else

max=h2;

return 1+max;

}

int countnode(tnode *p)

{

int c1=0,c2=0;

if(p==NULL)

return 0;

if(p->left)

c1=countnode(p->left);

if(p->right)

c2=countnode(p->right);

return 1+c1+c2;

}

int internal(tnode *p)

{

int i1=0,i2=0;

if(p->left==NULL && p->right==NULL)

return 0;

if(p->left) //!=NULL)

i1=internal(p->left);

if(p->right) //!=NULL)

i2=internal(p->right);

return 1+i1+i2;

}

int leaf(tnode *p)

{

int l1=0,l2=0,count=0;

if(p==NULL)

return 1;

if(p!=NULL)

{

if(p->left==NULL && p->right==NULL)

count++;

if(p->left)

l1=leaf(p->left);

if(p->right)

l2=leaf(p->right);

}

return count+l1+l2;

}

tnode *delmin(tnode *p)

{

tnode *temp=p,*r;

while(temp->left->left!=NULL)

{ temp=temp->left; }

r=temp->left;

temp->left=temp->left->right;

delete r;;

return p;

}

tnode *delmax(tnode *p)

{

tnode *temp=p,*r;

while(temp->right->right!=NULL)

{ temp=temp->right; }

r=temp->right;

temp->right=temp->right->left;

delete r;

return p;

}

int sum(tnode *p)

{

int s1=0,s2=0;

if(p==NULL)

return 0;

if(p!=NULL)

{

s1=sum(p->left);

s2=sum(p->right);

return s1+s2+p->data;

}

}

void complete(tnode *p)

{

int h=height(p);

int t=(int)pow(2,float(h)-1);

if(t==1)

cout<<"\n\n its complete tree :";

else

cout<left && !p->right) || (!p->left && p->right) )

{ flag=1; return flag; }

else

{ if(!flag)

{flag=strict(p->left);

flag=strict(p->right);}

}

}

if(flag==0)

cout<<"\n its strict bst ";

else

cout<left);

mirror(p->right);

tnode *temp;

temp=p->left;

p->left=p->right;

p->right=temp;

}

return p;

}

bool identical(tnode *p,tnode *q)

{

if(p==NULL && q==NULL)

return(true);

else if(p!=NULL && q!=NULL)

return (p->data==q->data && identical(p->left,q->left) && identical(p->right,q->right));

else

return false;

}

int search( tnode *p, int val)

{

if(p==NULL)

return -1;

int level=0;

struct tnode *q=p,*temp;

while(q!=NULL)

{

temp=q;

if(val data)

{q=temp->left;

level++; }

else if(val >temp->data)

{q=temp->right;

level++; }

else if(val == temp->data)

return level;

}

return -2;

}

void display(tnode *p,int val)

{

if(search(p,val)==-2)

cout<<"\n\n "<<val< is not present in bst :";

else if(search(p,val)==-1)

cout<<"\n\n bst is NULL";

else

cout<<"\n\n ("<<val<is at ("<<search(p,val)<data)

{ flag=level; break; }

else if(valdata)

{ q=q->left;

level++; }

else if(val>q->data)

{ q=q->right;

level++; }

}

//flag=-2;

if(flag==-1)

cout<<"\ntree is empty ";

else if(flag==-2)

cout<<"\n data is not in bst ";

else

cout<<level<<endl;

}

*/