Some Normal Codes of Binary Tree and Binary Search Trees :)

A  Binary search tree (BST), sometimes also called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtree must each also be a binary search tree.

• There must be no duplicate nodes. 

I assume you know very well the insertion ,searching ,and some basics so I am not explain here . For more information refer Wikipedia .

Deletion

There are three possible cases to consider:

• Deleting a leaf (node with no children): Deleting a leaf is easy, as we can simply remove it from the tree.
• Deleting a node with one child: Remove the node and replace it with its child.
• Deleting a node with two children: Call the node to be deleted N. Do not delete N. Instead, choose either its in-order successor node or its in-order predecessor node, R. Replace the value of N with the value of R, then delete R.

As with all binary trees, a node's in-order successor is the left-most child of its right subtree, and a node's in-order predecessor is the right-most child of its left subtree. In either case, this node will have zero or one children. Delete it according to one of the two simpler cases above.

 #include<string.h>
#include<cstdlib>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<iostream>
using namespace std;
struct node{
    int data;
    struct node* left;
    struct node* right;
};
struct Link_list_address_return
{
    struct node* first;
    struct node* last;
};
struct node* NEW(int i)
{
struct node* NODE=(struct node*)malloc(sizeof(struct node));
NODE->data=i;
NODE->left=NULL;
NODE->right=NULL;
return (NODE);
}
struct node* CASE1(struct node* root,struct node* par,struct node* Node)  /*FOR LEAF NODE */
{
    if(par==NULL)
        root=NULL;
    else if(Node==par->left)
        par->left=NULL;
    else
        par->right=NULL;
    free(Node);
return root;
}
struct node* CASE2(struct node* root,struct node* par,struct node* Node)  /*NODE HAVING ONLY ONE CHILD */
{
struct node *temp;
if(Node->left!=NULL)
    temp=Node->left;
else
    temp=Node->right;
if(par==NULL)
    root=temp;
else if(Node==par->left)
    par->left=temp;
else
    par->right=temp;
free(Node);
return root;
}
struct node* CASE3(struct node* root,struct node* par,struct node* Node)  /*NODE HAVE BOTH CHILD */
{
   struct node *succ,*parsucc;
   parsucc=Node;
   succ=Node->right;
   while(succ->left!=NULL)
   {
       parsucc=succ;
       succ=succ->left;
   }
   Node->data=succ->data;
   if(succ->left==NULL&&succ->right==NULL)
       root=CASE1(root,parsucc,succ);
   else
       root=CASE2(root,parsucc,succ);
   return root;
}
struct node* DEL(struct node* root,int val)
{
    struct node *par,*Node;
    Node=root;
    par=NULL;
    while(Node!=NULL)
    {
        if(val==Node->data)
            break;
        par=Node;
        if(val < Node->data)
            Node=Node->left;
        else
            Node=Node->right;
    }
    if(Node==NULL)
        printf("value %d is not present in the tree\n",val);
    else if(Node->left!=NULL&&Node->right!=NULL)
        root=CASE3(root,par,Node);
    else if(Node->left==NULL&&Node->right==NULL)
        root=CASE1(root,par,Node);
    else
        root=CASE2(root,par,Node);
    return root;
}
int LCA_OF_BST(struct node* root,int v1,int v2) //v1 < v2
{
    int data=root->data;
    int x=min(v1,v2),y=max(v1,v2);
    v1=x,v2=y;
    if(root==NULL ||data==v1||data==v2)
        return -1;  //No_Lowest_Common_Ancestor
    else if(data>v1&&data<v2)
        return data;
    else if(data>v1&&data>v2)
        return LCA_OF_BST(root->left,v1,v2);
    else if(data<v1&&data<v2)
        return LCA_OF_BST(root->right,v1,v2);
}
struct node* insertBST(struct node* root,int data)
{
    if(root==NULL)
    {
        root=NEW(data);
        return root;
    }
    else if(root->data>data)
        root->left=insertBST(root->left,data);
    else if(root->data<data)
        root->right=insertBST(root->right,data);
    else
        printf("Duplicate element exist\n");
    return root;
}
void traverseBST(struct node* root,int ttype)   //1.pre_order 2.inorder 3.postorder  ttype :traversal type preorder,postorder,inorder
{    if(root==NULL)
        return ;
    switch(ttype)
    {
        case 1:
            printf("%d ",root->data);
            traverseBST(root->left,1);
            traverseBST(root->right,1);
            break;
        case 2:
            traverseBST(root->left,2);
            printf("%d ",root->data);
            traverseBST(root->right,2);
            break;
        case 3:
            traverseBST(root->left,3);
            traverseBST(root->right,3);
            printf("%d ",root->data);
            break;
    }

}
int LEAFCOUNT(struct node *root)
{
    if(root==NULL)
        return 0;
    if(root->left==NULL&&root->right==NULL)
        return 1;
    return (LEAFCOUNT(root->left)+LEAFCOUNT(root->right));
}
struct Link_list_address_return* THEGREATTREERECURSIONLIST(struct node* root)
{
     struct Link_list_address_return *RET,*RET1,*RET2;
     RET=(struct Link_list_address_return *)malloc(sizeof(struct Link_list_address_return));
     RET1=(struct Link_list_address_return *)malloc(sizeof(struct Link_list_address_return));
     RET2=(struct Link_list_address_return *)malloc(sizeof(struct Link_list_address_return));
     if(root==NULL)
     {
     printf("TREE IS EMPTY\n");
     RET->first=NULL;
     RET->last=NULL;
     return RET;
     }
     if(root->left==NULL&&root->right==NULL)  //leaf node condition
     {
     //RET=(struct Link_list_address_return *)malloc(sizeof(struct Link_list_address_return));
     RET->first=root;
     RET->last=root;
     root->left=root;
     root->right=root;
     // cout<<"leaf \n";
     return RET;
     }
     else if(root->left!=NULL&&root->right==NULL)  //have only left subtree
     {
         //   cout<<"left \n";
            RET1=THEGREATTREERECURSIONLIST(root->left);
        root->left=RET1->last;
        root->right=RET1->first;
        RET1->first->left=root;
        RET1->last->right=root;
        RET1->last=root;
        return RET1;

     }
     else if(root->left==NULL&&root->right!=NULL)  //have only right subtree;
     {

          //  cout<<"right \n";
            RET1=THEGREATTREERECURSIONLIST(root->right);
            root->left=RET1->last;
            root->right=RET1->first;
            RET1->first->left=root;
            RET1->last->right=root;
            RET1->first=root;
                return RET1;

     }
     else if(root->left!=NULL&&root->right!=NULL)  //have both subtree ;
     {
        // cout<<"both before\n";
         RET1=THEGREATTREERECURSIONLIST(root->left);
         RET2=THEGREATTREERECURSIONLIST(root->right);
         root->left=RET1->last;
         root->right=RET2->first;
         RET1->last->right=root;
         RET1->first->left=RET2->last;
         RET2->last->right=RET1->first;
         RET2->first->left=root;
         RET1->last=RET2->last;
        // cout<<"both after\n";
         return RET1;
     }

}
void PRINTDOUBLYLINKLIST(struct node *head,struct node *tail)
{
    if(head==NULL)
    {
            printf("Doubly Link List is empty\n");
        return ;
        }
    else if(head==tail)
    {
        printf("%d ",head->data);
        return ;
    }
    else {
        printf("%d ",head->data);
        PRINTDOUBLYLINKLIST(head->right,tail);
        return ;
    }

}
bool isleaf(struct node *root)
{
   if(root->left==NULL&&root->right==NULL)
   return true;
   return false;
}
bool have_left_child(struct node *root)
{
return !(root->left==NULL);
}
bool have_right_child(struct node *root)
{
return !(root->right==NULL);
}
int childrensumproperty(struct node *root,int increment=0)  //for first call increment=0;
{
    int diff,totalincrement;
    if(isleaf(root))
    {
       // cout<<"leaf";
       root->data+=increment;
       return 0;
    }
    root->data+=increment;
    diff=root->data-(have_left_child(root)?root->left->data:0)-(have_right_child(root)?root->right->data:0);
    if(diff==0)  //case 1:
    {
        totalincrement=(have_left_child(root)?childrensumproperty(root->left):0)+(have_right_child(root)?childrensumproperty(root->right):0);
         root->data+=totalincrement;
         return totalincrement;
    }
    else if(diff<0)
    {
        root->data-=diff;  //to add the difference bcz diff is negative so -diff is > 0
        totalincrement=(have_left_child(root)?childrensumproperty(root->left):0)+(have_right_child(root)?childrensumproperty(root->right):0);
         root->data+=totalincrement;
         totalincrement-=diff;
         return totalincrement;
    }
    else if(diff > 0 )
    {
        //case 1 for left child increment only
        if(have_left_child(root))
        {
        totalincrement=(have_left_child(root)?childrensumproperty(root->left,diff):0)+(have_right_child(root)?childrensumproperty(root->right):0);
       // root->data+=(have_left_child(root)?childrensumproperty(root->left,diff):0)+(have_right_child(root)?childrensumproperty(root->right):0);
        root->data+=totalincrement;
        }
        else if(have_right_child(root))
        {
        totalincrement=(have_left_child(root)?childrensumproperty(root->left):0)+(have_right_child(root)?childrensumproperty(root->right,diff):0);
       //root->data+=(have_left_child(root)?childrensumproperty(root->left):0)+(have_right_child(root)?childrensumproperty(root->right,diff):0);
        root->data+=totalincrement;
        }
        return totalincrement;
    }
  
  
}
int Diameter_of_Tree(struct node *root,int *height)
{
/*complexity is O(n) */
    int lh=0,rh=0;
    int ld=0,rd=0;
    if(root==NULL)
        {
        *height=0;
        return 0;
        }
    ld=Diameter_of_Tree(root->left,&lh);
    rd=Diameter_of_Tree(root->right,&rh);
    *height=max(lh,rh)+1;
    return max(lh+rh+1,max(ld,rd));
}
bool isAVL(struct node *root,int *height)
{
bool b1,b3,b2=false;
int lh,rh;
      if(root==NULL)
      {
      *height=0;
      return true;
      }
      b1=isAVL(root->left,&lh);
      if(b1==false)
      return false;
      b2=isAVL(root->right,&rh);
      if(b2==false)
      return false;
      *height=max(lh,rh)+1;
      if(abs(lh-rh)>=2)
      return false;
      else
      return true;
}
/*
Total number of possible Binary Search Trees with n keys = Catalan number Cn = (2n)!/(n+1)!*n!
*/
struct node* Mirror(struct node* root)
{
     struct node *temp;
     if(root==NULL)
     return NULL; //for NULL
     temp=root->left;
     root->left=root->right;
     root->right=temp;
     root->left=Mirror(root->left);
     root->right=Mirror(root->right);
     return root;
}
bool isStructSame(struct node *r1,struct node* r2)
{
      if(r1==NULL&&r2==NULL)
      return true;
      if(r1!=NULL&&r2!=NULL&&isStructSame(r1->left,r2->left)&&isStructSame(r1->right,r2->right))
      return true;
      return false;
}
void isFoldable(struct node* root)
{
/*
   A tree can be folded if left and right subtrees of the tree are structure wise mirror image of each other. An empty tree is considered as foldable.
*/
    if(root==NULL)
        {
            cout<<"Tree is Foldable\n";
            return ;
        }
    root->left=Mirror(root->left);   // get Mirror image of left subtree
    bool flag=isStructSame(root->left,root->right);
    root->left=Mirror(root->left);  //to change the tree before mirror is Inverse Mirror
    if(flag)
        {
                cout<<"Tree is Foldable\n";
            return ;  
        }
    else
        {
                cout<<"Tree is Not Foldable\n";
            return ;
        }
//if flag is False then not foldable else flodable
return ;
}
struct node* Make_Bst(struct node* root)
{
     printf("Enter number of elements to insert in tree \n");
     int n,data;
     cin>>n;
     for(int i=0;i<n;i++)
     {
        cout<<"enter the value u want to push in the tree \n";
        cin>>data;
        root=insertBST(root,data);
     }
     return root;
}
struct node* make_test_tree(struct node *root)
{
      root=NEW(10);
      root->left=NEW(7);
      root->right=NEW(15);
      root->left->left=NEW(5);
      root->right->left=NEW(11);
      return root;
    
}
struct node* minvalue(struct node *root)
{

        if(root==NULL)
        {
           printf("No minimum value exist");
           return NULL;
        }
        cout<<root->data<<" \n ";
        if(root->left==NULL)
        {
           cout<<"hi i m";
           printf("Minimum value is %d",root->data);
           return root;
        }
        if(root->left!=NULL)
        {
           while(root->left!=NULL)
           {
             root=root->left;
           }
           printf("Minimum value is %d",root->data);
           return root;
        }
}
struct node* inorderSuccessor(struct node* root,struct node* Node)
{
    struct node *succ;
      if(Node->right!=NULL)
       {
       cout<<"hi"<<Node->data<<" ";
       succ=minvalue(Node->right);
       return succ;
       }
       succ=NULL;
       while(root!=NULL)
       {
            if(Node->data<root->data)
            {
            succ=root;
            root=root->left;
            }
            else if(Node->data > root->data)
                root=root->right;
            else
                break;
              
       }
       return succ;
}
int Kth_smallest_element(struct node* root,int k)
{
    int pop_count=0;
    stack <struct node*> S;
    if(root==NULL)
    {
        printf("No element in the Binary Search Tree\n");
        return -1;  //on error
    }   //NO result
    S.push(root);
    struct node *temp1;
    temp1=root;
    while(!S.empty())
    {
          if(temp1->left!=NULL)
          {
              while(temp1->left!=NULL)
              {
                  S.push(temp1->left);
                  temp1=temp1->left;
              }
          }
          else
          {
              temp1=S.top();
              S.pop();
              pop_count++;
              if(pop_count==k)
              return temp1->data;
              while((!S.empty())&&temp1->right==NULL)
              {
                  temp1=S.top();
                  S.pop();
                  pop_count++;
                  if(pop_count==k)
                     return temp1->data;
              }
              if(temp1->right!=NULL)
              {
                  S.push(temp1->right);
                  temp1=temp1->right;
              }
             
          }
    }
  
    printf("\nError : The number of Nodes in the BST in less than K\n");
    return -1;
}
int level_of_node(struct node* root,int key,int level=1)
{
/* this function works for any Binary Tree not only for BST*/
    if(root==NULL)
        return 0;
    if(root->data==key)
        return level;
    return level_of_node(root->left,key,level+1) | level_of_node(root->right,key,level+1);
}
bool printAll_Ancestor(struct node* root,int key)
{
  if(root==NULL)
  return false;
  if(root->data==key)
  return true;
  if( printAll_Ancestor(root->left,key)||printAll_Ancestor(root->right,key))
  {
      printf("%d ",root->data);
      return true;
  }
  return false;
}
void print_keys_in_range(struct node *root,int k1,int k2)   //k1<=key<=k2  valid for BST
{
   if(root==NULL)
   return ;
   if(root->data>k1)
      print_keys_in_range(root->left,k1,k2);
   if(root->data>=k1&&root->data<=k2)
      printf("%d ",root->data);
   if(k2>root->data)
      print_keys_in_range(root->right,k1,k2);
   return ;
}
int main()
{
int height=0;
struct node* root=NULL;
struct node *r1=NULL,*r2=NULL;
//root=insertBST(root,2);
/*root=insertBST(root,15);
root=insertBST(root,10);
root=insertBST(root,8);
root=insertBST(root,16);
root=insertBST(root,17);*/
root=Make_Bst(root);
traverseBST(root,2);
//print_keys_in_range(root,1,35);
//printf("\n")&&printAll_Ancestor(root,4);
//cout<<"\n"<<Kth_smallest_element(root,18)<<endl;
//cout<<"\nLevel of the key :"<<level_of_node(root,13)<<endl;
//root=make_test_tree(root);
//isFoldable(root);
//struct Link_list_address_return *RET;
//root=DEL(root,1);
//r1=Make_Bst(r1);
//r2=Make_Bst(r2);
//traverseBST(root,2);
//root=Mirror(root);
//cout<<LCA_OF_BST(root,3,5);
//childrensumproperty(root);
//cout<<"\n";
//traverseBST(root,1);
//cout<<"\n Inorder Successor :"<<inorderSuccessor(root,root->left)->data<<"\n";
//cout<<"\n Diameter of Tree :"<<Diameter_of_Tree(root,&height);
//RET=THEGREATTREERECURSIONLIST(root);
//PRINTDOUBLYLINKLIST(RET->first,RET->last);
return 0;
}