1. Given the following output, draw the binary search tree. Inorder : EICFJBGDKHLA PreOrder : ABCEIFJDGHKL

The method for obtaining tree is as follows
1) get the ith character from preorder output
2) Find its index in inorder - idx
3) All values of the subtree to the left of idx are in left subtree
4) All values to right of idx are on right subtree

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
    char val;
    struct node *left;
    struct node *right;
};

struct node *createnode(char ch)
{
    struct node *newnode =(struct node*) malloc(sizeof(struct node));
    newnode->val = ch;
    newnode->left = newnode->right = NULL;
    return newnode;
}

int findindex(char *inorder,char ch)
{
     int i;
     for(i=0;inorder[i]!=0&&inorder[i]!=ch;i++);
     return i;
}

struct node * constructNode(char *preorder,char *inorder,int instart,int inend)
{
    static int preindex = 0;
    if( instart>inend)
       return NULL;
 
    char ch = preorder[preindex++];
  /*  printf("ch is %c\n instart is %d inend is %d",ch,instart,inend);*/
    struct node * nd = createnode(ch);
    if(instart==inend)
       return nd;
    int l = strlen(inorder);

    int index = findindex(inorder,ch);
    struct node * left = constructNode(preorder,inorder,instart,index-1);
    struct node * right = constructNode(preorder,inorder,index+1,inend);
    nd->left = left;
    nd->right = right;
    return nd;
}
 
void inorderprint(struct node *nd)
{
  if(nd!=NULL)
  { 
    inorderprint(nd->left);
    printf("%c----->",nd->val);
    inorderprint(nd->right);
   }
}
int main()
{
    char inorder[30],preorder[30];
    struct node *root;
    printf("Enter inorder output");
    scanf("%s",inorder);
    printf("Enter preorder output");
    scanf("%s",preorder);
    root = constructNode(preorder,inorder,0,strlen(preorder)-1);
    printf("\n Inorder traversal is ");
    inorderprint(root);
}

2. Write an algorithm to add a new node non-recursively to a binary search tree and write a function for this.

Algorithm for adding a node to binary search tree
1) set node = root
2) set parent = node
3) if newnode > node, set node to node->right
4) If newnode < node, set node to node->left
5) repeat steps 2 to 4 until node is null
6) if key of newnode>key of parent, set parent ->right = newnode
7) if not set parent->left = newnode

If root is NULL, then we should set root = newnode.

NODEPTR insert_node_nr(NODEPTR nd,NODEPTR newnode)
{
     NODEPTR parent = nd;
     NODEPTR root = nd;
     if(root == NULL)
        return newnode;
    /*find a location add new node*/
     while(nd!=NULL)
     {
        parent = nd;
        if(newnode->val > nd->val)
            nd = nd->right;
        else if(newnode->val <nd->val)
           nd = nd->left;
        else
        {
               printf("Duplicate values not allowed");
               return NULL;
         }
     }
     if(newnode->val >parent->val)
         parent->right = newnode;
     else
         parent->left = newnode;
     return root;
}

int main()
{
      NODEPTR root = NULL;
      NODEPTR newnode;
    .....
     int n ;
     scanf("%d",&n);
     newnode = create_node(n);
     root = insert_node_nr(root,newnode);
  .....
}

3. Write algorithms for deleting a node from a binary search tree in all possible cases.

When a node is to be deleted from a binary search tree, there are 3 possible cases
a) the node is leaf
b) the node has only one child/subtree
c) the node has both children/subtrees

The following recursive algorithm takes care of all three cases

1) nd = root

find the node to be deleted
2) if nd->val > delvalue
recursively call delete on nd->left and set result to nd->left
3) if nd->val < delvalue
recursively call delete on nd->right and set result to nd->right

node is found
4) if nd->val==delvalue
a)if nd is a leaf node return NULL so that parent->left or parent->right is NULL after deleting nd
b) if nd has only one non-null child, return non-null child. parent->left or parent->right is set to nd->child
c) If nd has both children, find in order successor of nd.
i) copy sucessor's value to nd
ii) set node to be deleted (nd) to successor
iii) Delete this inorder successor using either a or b above. because successor will be either be leaf or will have only right child

/* inorder successor is the minimum of 
right subtree*/
NODEPTR find_rightst_min(NODEPTR node)
{
     node = node->right;
     while(node->left!=NULL)
       node = node->left;
     return node;
}
NODEPTR delete_node(NODEPTR nd,int delval)
{
    if(nd==NULL)
       return nd;
    if(nd->val >delval)
        nd->left = delete_node(nd->left,delval);
     else if(nd->val < delval)
        nd->right = delete_node(nd->right,delval);
     else/*node found*/
     {
        if(nd->left==NULL && nd->right==NULL)/*leaf node*/
         {
             free(nd);
     	  nd = NULL;
         }
        else if(nd->left==NULL)/*has only right child*/
        {
           NODEPTR temp = nd->right;
           free(nd);
           nd =temp;
        }
        else if(nd->right==NULL)/*has only left child*/
        {
           NODEPTR temp = nd->left;
           free(nd);
           nd = temp;
        }
        else/*has both subtrees*/
         {
          NODEPTR min_node = find_rightst_min(nd);
          nd->val = min_node->val;
          nd->right = delete_node(nd->right,min_node->val);
         }      
      }
    return nd;  
}

4. Explain one way and two way threaded binary trees

A threaded binary is the one which uses the NULL pointers of nodes to store links to in order successor and in order predecessor. These links are called threads.

A one way threaded binary tree will have only one type of threads - either inorder successor or inorder predecessor.

Two way threaded binary tree has threads for both inorder successor and inorder predecessor.

Threaded binary tree uses up wasted NULL links and allows you to traverse the tree non-recursively.

Now a node can have left pointer either as a left child or a left thread. Similar is the case with right pointer.

To differentiate between the two, two extra boolean variables are used in each node - isLeftThread and isRightThread which are set to 1 to indicate thread and reset to 0 to indicate child nodes.

5. Draw a binary heap from the elements shown below. And also write a program to heap sort an array. 50 25 30 75 100 45 80

A binary heap is a special binary tree where every node has a value greater than its children (max heap).

In a min heap, every node has key value smaller than that of its children.

Heap sort arranges the elements in a max heap (heapify). Then it swaps the root element with last element and reduces the size of heap by one. Then the heap is built again. This procedure is continued till array is sorted.

#include <stdio.h>
void printArray(int *arr,int n);
void swap(int *a,int *b)
{
     int temp = *a;
    *a = *b;
    *b = temp;
}
 
/* convert node at index i into a max heap */
void heapify(int arr[], int n, int i)
{     
    int largest = i;  
    int left = 2*i + 1;  /* left child = 2*i + 1*/
    int right = 2*i + 2;  /* right child = 2*i + 2*/
     
    if (left < n && arr[left] > arr[largest])
        largest = left;
   
    if (right < n && arr[right] > arr[largest])
        largest = right;
    
    if (largest != i)    {
        swap(&arr[i], &arr[largest]);        
        heapify(arr, n, largest);/*now node at largest may be out of order. heapify it*/
    }
}

void heapSort(int arr[], int n)
{
    int i;
    /* Build heap from array elements*/
    for ( i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
 
    /*Extract 0th element (root) and move it at the end of array. Reduce the size of heap*/
    for ( i=n-1; i>=0; i--)
    {
        /* Move current root to end*/
        swap(&arr[0], &arr[i]);

        /* call max heapify on the reduced heap*/
        heapify(arr, i, 0);
    }
}

void readArray(int arr[], int n)
{
    int i;
    for ( i=0; i<n; ++i)
    {
        printf("a[%d]",i);
        scanf("%d",&arr[i]);
    }  
} 

void printArray(int arr[], int n)
{
    int i;
    for ( i=0; i<n; ++i)
        printf("%d ",arr[i]);
   printf( "\n");
}

 
int main()
{
    int arr[40];int n; 
    printf("What is array size");
    scanf("%d",&n);
    readArray(arr,n);
    
    heapSort(arr, n);

    printf("Sorted array is \n");
    printArray(arr, n);
}

6. Write a function to find the number of leaf nodes in a given binary tree.

We can write a recursive function for this.
count = leaf nodes in left subtree + leaf nodes in right subtree

If a node is having left link as NULL and right link as NULL, then it is a leaf node. So if this condition is true, the call should return 1. If the node is NULL, the call should return 0.

if node is NULL
return 0
if node->left==NULL and node->right==NULL
return 1
else
return count(node->left)+count(node->right)

int count_leaf_nodes(NODEPTR nd)
{
    if(nd==NULL)
       return 0;
    if(nd->left ==NULL  && nd->right==NULL)
       return 1;
     
       return count_leaf_nodes(nd->left)+count_leaf_nodes(nd->right);
}

7. Write a function to find in order successor of a given non-leaf node in a binary tree

In order successor a node is the node which is encountered next in the inorder traversal.

And this node will be tree minimum of right subtree of the given node.

If the node has a right child, we branch to right. Next we traverse left until node->left is NULL. At this point, we have got our inorder successor.

If it does not have a right child, then in-order successor is the bottom-most ancestor which branched to left. That is - in order successor is the parent of last node which was a left child. So parent of 150 is 900 and parent of 58 is 100.

e.g.
100
10 900
2 58 150 1090

In the tree shown above, in order successor of 10 is 58. Inorder successor of 100 is 150

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d---",nd->val);
        in_order(nd->right);
     }
}
NODEPTR search(NODEPTR nd,int num)
{
    while(nd!=NULL )
    {
        if (num > nd->val)
           nd = nd->right;
        else if (num< nd->val)
           nd = nd->left;
        else 
           return nd;
     }
     return NULL;/*not found*/
}

NODEPTR successor(NODEPTR root, NODEPTR nd)
{
     if(nd->right!=NULL)
     {
         nd = nd->right;
         while(nd->left!=NULL)
         { 
             nd = nd->left;
         }
         return nd;
     }
     else
     {
        NODEPTR succ = NULL;
        while(root!=NULL)
        {
            if(root->val > nd->val)
            {
                 succ = root;
        	root = root ->left;
            }
            else if(root->val <nd->val)
                root = root ->right;
            else
                return succ;
        }
        return root;
    } 
}

int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1); 
       printf("\nInorder traversal\n");
       in_order(root);  
       while(1)
       {   
         printf("Enter node value (-1 to stop):");
         scanf("%d",&n);
         if(n==-1)
            break;
         NODEPTR nd = search(root,n);
         if(nd==NULL)
             printf("%d is not present in tree",n);
         else
            {
             NODEPTR nds = successor(root,nd);
             if(nds!=NULL)
                printf("the successor is %d\n",nds->val);
             else
                printf("No successor\n");
            }
       }    
       return 0;
}

8. Explain what is binary search tree with an example. Write a function to search a value in a binary search tree using iteration.

A binary tree is a non-linear data structure where each node has two child pointers to left child node and right child node and data. The top most node is called root node.

A binary search tree is a binary tree with the special property that each node has nodes with smaller key values on left sub tree and larger key values on right subtree. So a binary search tree (BST) is ordered.

Inorder traversal of binary search tree gives key values in ascending order.

Searching a value in a BST is done in O(logn) time. For searching, we compare the node and if search value is greater than node value, we branch to right. If search value is smaller than node value, we branch to left. This is repeated until search value is found or we get a NULL. If such a branch gives us NULL, then the value is not found.

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR search_node(NODEPTR root, int num)
{
   NODEPTR temp = root;
   while(temp!=NULL)
   {
      if(temp->val>num)
         temp = temp->left;
      else if(temp->val<num)
         temp = temp->right;
      else/*we found a match*/
         return temp;
   }
   return NULL;/*no match*/
} 
NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d---",nd->val);
        in_order(nd->right);
     }
}
int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
       
       printf("\nInorder traversal\n");
       in_order(root);
      
       while(1)
       {
          NODEPTR snode;
          printf("Enter value to search (-1 to quit):");
          scanf("%d",&n);
          snode = search_node(root,n);
          if(snode==NULL)
             printf("Value not found\n");
          else 
             printf("Value is found\n");
       }
       return 0;
}

9. Write a function for inorder traversal of a threaded binary tree

Threaded binary trees are invented to avoid recursion while traversing the binary tree.

Every node in a threaded binary tree except for terminal nodes will have both left and right links. If the node does not have a child node, then links are threads to inorder predecessor(left link) and inorder successor(right link).

To travese such a tree, you need to find tree minimum. That is done by moving to node->left until there is left thread.
Then you just need to
continue to set node = node->right if you have right thread
else go to tree minimum of right subtree if there is right child

Continue this until you reach tree maximum

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
   int isleftthread;
   int isrightthread;
};
typedef struct node *NODEPTR;

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     temp->isleftthread = 1;
     temp->isrightthread = 1;
     return temp;
}

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
     NODEPTR parent = nd;
     NODEPTR root = nd;
     if(root == NULL)
       return newnode;
     while(nd!=NULL)
     {
       parent = nd;
       if(newnode->val > nd->val)
       {
         if(nd->isrightthread)
         {
           nd = nd->right;
           break;
         }
         else
            nd = nd->right;	
       } 	
       else if(newnode->val <nd->val){
         if(nd->isleftthread)
 	 {
            nd = nd->left;
            break;
         }
         else
           nd = nd->left;
        }
        else
        {
           printf("Duplicate values not allowed");
           return NULL;
         }
     }
     if(newnode->val >parent->val)
	{/*insert as right child*/
	newnode->right = parent->right;
	parent->right = newnode;
	parent->isrightthread=0;
	newnode->left = parent;/*update thread*/
	}
     else
	{/*insert as left child*/
	newnode->left = parent->left;
 	parent->left = newnode;
	parent->isleftthread = 0;
	newnode->right = parent;/*update thread*/
	}
     return root;
}
void in_order(NODEPTR nd)
{
    /* find extreme left node*/
    while(!nd->isleftthread)
	nd = nd->left;
   /* traverse all nodes till extreme right end*/
    while(nd)
	{
	  printf("%d  ",nd->val);
	  if(nd->isrightthread)
             nd = nd->right;
          else 
            {/*find tree minimum of right subtree*/
              nd = nd->right;
              while(nd!=NULL && !nd->isleftthread)
                nd = nd->left;
           }
	} 
}

void pre_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        printf("%d---",nd->val);   
        pre_order(nd->left);
        pre_order(nd->right);
            
     }
} 
 
int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
       
       printf("\nInorder traversal\n");
       in_order(root);
       return 0;
}

10. Given a binary tree, write a function to find the depth of a binary tree.

The depth or height of a binary tree is the distance between the root node and farthest leaf node.

The function recursively finds the height of a tree.

If the node is NULL, it returns -1.

If the node is not NULL, then it returns
1+ maximum(height of left subtree, height of right subtree)

int find_height(NODEPTR nd)
{
   if(nd==NULL)
      return -1;
   else
     {
        int h1 = find_height(nd->left);
        int h2 = find_height(nd->right);
        h1 = h1>h2?h1:h2;/*maximum of heights of left subtree and right subtree */
        return  h1+1;
     }
}

11. Write a function to print the nodes in ascending order of a binary tree

The inorder traversal of a binary search tree will print the nodes in ascending order.

The method of traversal is
1) Visit the left subtree
2) Visit the current node
3) Visit the right subtree

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d--->",nd->val);
        in_order(nd->right);
     }
}

12. Write recursive functions for implementing tree traversal techniques - all of the three - inorder, preorder and postorder

Binary tree can be traversed in 3 different ways - inorder, preorder and postorder. In in-order traversal, the current node is traversed after left subtree and before right subtree. In pre-order current node is visited before its sub-trees. In post-order, current node is visited after visiting the sub-trees.

Inorder traversal- For any node
1) Traverse left subtree
2) visit current node
3) Traverse right subtree

Preorder traversal -
1) visit current node
2) Traverse left subtree
3) Traverse right subtree
Remember that in preorder traversal, root is visited first.

Postorder traversal -
1) Traverse left subtree
2) Traverse right subtree
3) visit the current node
In post order traversal, root node is visited last.

If we have a tree like this
10
2 45
1 5 22 800

with just 3 nodes, say root as 100, 30 as its left child and 400 as its right child, then the traversals will be
Inorder : 1 2 5 10 22 45 800
Preorder : 10 2 1 5 45 22 800
Postorder: 1 5 2 10 22 800 10

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d--->",nd->val);
        in_order(nd->right);
     }
}

void pre_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        printf("%d--->",nd->val);   
        pre_order(nd->left);
        pre_order(nd->right);            
     }
}

void post_order(NODEPTR nd)
{
   if(nd!=NULL)
    {    
        post_order(nd->left);
        post_order(nd->right);
        printf("%d--->",nd->val);
     }
}

13. Write a function to insert a node into a binary search tree using recursion

In a BST, the nodes are arranged in such a way that for any node, its left subtree has values smaller than current node and right subtree has values larger than current node.

So to insert a node, we should find a leaf node in the correct path depending on the value of newnode.

We compare the newnode value with current node. If newnode is larger, we call this function recursively for right child. If newnode is smaller , we call the function recursively for left child. This is continued until we reach null. If a node is NULL, we return newnode.

create_node function which allocates memory, assigns value is not shown in the code.

struct node
{
   int val; 
   struct node *left,*right;
};
typedef struct node *NODEPTR;
NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode; 
    if(newnode->val > nd->val)/*branch to right*/
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)/*branch to left*/
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}
int main()
{
    NODEPTR root = NULL;
    root = insert_node(root,create_node(10));
    root = insert_node(root,create_node(22));
    root = insert_node(root,create_node(3));
   ....
}

14. Explain the following terms 1) Strictly binary tree 2) Complete binary tree 3) Balanced binary tree

A strictly binary tree is a binary tree where each node has either 0 child nodes or 2 child nodes. That is, in a strictly binary tree, all non-leaf nodes have 2 children.

A complete binary tree has all the levels completely filled except for last level, which is filled from left to right. A heap is an example of complete binary tree.

A balanced binary tree is a binary tree where the height of left subtree and height of right subtree are almost equal. AVL tree is an example of balanced binary tree.

15. Given a list of numbers, write a program to create a binary search tree, avoiding duplicate numbers.

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
}
NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)/*branch to right*/
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)/*branch to left*/
        nd->left = insert_node(nd->left,newnode); 
    else
   {
	printf("Duplicate nodes are not allowed");
    }
    return nd;   
}
void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d---",nd->val);
        in_order(nd->right);
     }
} 
int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);       
       printf("\nInorder traversal\n");
       in_order(root);         
       return 0;
}

16. What is a binary tree? Explain the following terms 1) root node 2) leaf node 3) ancestor 4) descedents 5) siblings

A tree is a non-linear data structure. A binary tree is a data structure where each node can be empty or can have a left subnode and a right subnode which are again binary trees. Left and right branches are called child nodes.

A tree data structure resembles an upside-down tree.

Root node is the starting node of a binary search tree similar to head of a linked list. It is the node which has no parent.

Leaf node is node in binary tree which has no child nodes. Left and right links of a leaf node will be null.

Sibling nodes are two nodes with the same parent node.

The nodes which are encountered in the path to the root node are called ancestors of a node.

The nodes which are encountered in the path to the leaf nodes are called a node's descendants

17. What is a heap? What are the different types of heap?

A heap is a complete binary tree with special property that any node will have a key value larger (max heap) than its children or smaller than its children (min heap).

A max heap will have largest key at the root. A min heap will have smallest key at the root.

A heap is used for implementing a priority queue.

Max heap example:
70
11 12
3 8 5

18. What are the different types of rotations in an AVL tree.

Four different types of rotations of an AVL tree are
1) Left rotation
2) Right rotation
3) Left-right rotation
4) Right-left rotation

When a right subtree is added to a right subtree and if the tree becomes unbalanced as a result of this, then single left rotation is performed.

If a tree becomes unbalanced when a left subtree is inserted to a left subtree, then a single right rotation is performed.

When a right subtree is added to left subtree and tree becomes unbalanced, a left right rotation is performed. First the child tree is rotated left. Next the subtree is rotated right.

When a left subtree is added to right subtree and tree becomes unbalanced, a right left rotation is performed.

19. What is an AVL tree? Write a program to insert a node to an AVL tree.

An AVL tree or an Adelson, Velsky and Landis tree is a self balancing binary search tree.

In an AVL tree, the difference between height of left subtree and height of right subtree is maintained to be in the range -1 to 1. This difference is called balance factor.

Each node stores its balance factor along with data and links. When the balance factor exceeds the range -1 to 1 during insertion or deletion of nodes, the nodes are rotated to maintain this balance factor.

The following tree is an AVL tree

100
10 500
2

This tree is not an AVL tree
100
10 500
120
145

#include<stdio.h>
#include<stdlib.h>
struct avlNode
{
   int num;
   struct avlNode *left;
   struct avlNode *right;
};
typedef struct avlNode *NDPTR;
int height(NDPTR temp)
{
    if(temp!=NULL)
    {
       int h1 = height(temp->left);
       int h2 = height(temp->right);
       return ( h1>h2?h1:h2)+1;
    }
    return 0;
}
int balance_factor(NDPTR temp)
{
     int h1 = height(temp->left);
     int h2 = height(temp->right);
     return h1-h2;
}

NDPTR rr_rotation(NDPTR parent)
{
     NDPTR temp = parent->right;
     parent->right = temp->left;
     temp->left = parent;
     return temp;
}

NDPTR ll_rotation(NDPTR parent)
{
     NDPTR temp = parent->left;
     parent->left = temp->right;
     temp->right = parent;
     return temp;
}

NDPTR lr_rotation(NDPTR parent)
{
    NDPTR temp = parent->left;
    parent->left = rr_rotation(temp);
    return ll_rotation(parent);
}
NDPTR rl_rotation(NDPTR parent)
{
    NDPTR temp = parent->right;
    parent->right = ll_rotation(temp);
    return rr_rotation(parent);
}
NDPTR balance(NDPTR temp)
{
    int bal_factor = balance_factor(temp); 
    if (bal_factor>1)
    {
       
       if(balance_factor(temp->left)>0)
          temp = ll_rotation(temp);
       else
          temp = lr_rotation(temp);
    }
    else if (bal_factor<-1)
    {
       if(balance_factor(temp->right)>0)
          temp = rl_rotation(temp);
       else
          temp = rr_rotation(temp);
    }
    return temp;
}
NDPTR create_node(int num)
{
  NDPTR temp = (NDPTR)malloc(sizeof(struct avlNode));
  temp->left = temp->right = NULL;
  temp ->num = num;
  return temp;
}
NDPTR insert(NDPTR root,int value)
{
     if(root==NULL)
     {
        root = create_node(value); 
     }
     else if(value>root->num)
     {
        root->right = insert(root->right,value);
        root = balance(root);
     }
     else if(value<root->num)
    {
        root->left = insert(root->left,value);
        root = balance(root);
     }
     return root;
}

void pre_order(NDPTR root)
{
    if(root!=NULL)
    {
       printf("\n%d ",root->num);
       pre_order(root->left);
       
       pre_order(root->right);
    }
}
int main()
{
   NDPTR root = NULL;
   while(1)
   {
      int n;
      printf("Enter a node to insert :");
      scanf("%d",&n);
      if(n==-1)
         break;
      root = insert(root,n);
   }
   pre_order(root);
}

20. What is a max heap? Write a function to add a value to a max heap.

A max heap is a complete binary tree with the heap property - that each node has a key value larger than those of its children. Root is the node with highest key value.

As a heap is a complete binary tree, that means all the levels of tree are filled except for last level which is filled from left to right. Which means that we can assign consecutive indices to elements of heap. And it can be implemented using an array.

When inserting a value into a max heap, the value is initiallly addded to the last element of array.

Now this node may not obey max heap property. So compare the newly added node to its parent. If it is larger than parent, swap it with parent. Now go up the tree, compare the parent node with its parent and so on. Repeat this until you reach the root. This is called heapification process.

In our implementation, we are omitting arr[0]. And we are taking arr[1] as root of heap. If we do this, for every node arr[i], its children are arr[2i] and arr[2i+1].

When we want to find the parent of a node k, it is arr[k/2].

 #include <stdio.h> 
void printArray(int *arr,int n);
void swap(int *a,int *b)
{
    int temp = *a;
   *a = *b;
   *b = temp;
}
  
void heapfilterup( int arr[],int k )
   {
      /*move newly added value up to maintain heap*/
      int parent=k/2;
      while ( parent > 0 )      
      {
       parent = k/2;   
      if ( arr[k]>arr[parent] )
      {    
         swap(&arr[parent],&arr[k]);
         k = parent;
      }
      else
      {
        break;    
      }
      }
   }

void insert(int arr[], int n, int newvalue)
{
     arr[n-1] = newvalue; 
     heapfilterup(arr,n-1);   
}

void readArray(int arr[], int n)
{
    int i;
    printf("Enter elements of the max heap in order:");
    for ( i=1; i<n; ++i)
    {
     printf("a[%d]",i);
     scanf("%d",&arr[i]);
   } 
} 

void printArray(int arr[], int n)
{
    int i;
    for ( i=1; i<n; ++i)
     printf("%d ",arr[i]);
   printf( "\n");
}

// Driver program
int main()
{
    int arr[40];int n,val; 
    printf("What is heap size");
    scanf("%d",&n);
    n++;
    readArray(arr,n);
   //we dont store a value at arr[0]
    printf("Enter new value to be inserted:");
    scanf("%d",&val);
    n++;
    insert(arr,n,val); 
    printf("Now the heap is \n");
    printArray(arr, n);
}

21. With the help of examples explain 1) Level of a binary tree 2) Depth of a binary tree

Level of any node in a binary tree is the distance between that node and root node.
Level of root is 0.

The depth of a binary tree is the level of the farthest leaf node. Depth of a tree is also called its height.

If we have a tree as shown below

100
10 500
2 18 300 900

Level of 100 is 0.
Level of 10 and 500 is 1
Level of 2, 18, 300 and 900 is 1

And height of tree is 2.

22. Write a program to covert a binary tree into sorted doubly linke list. Do not create any nodes but just modify links.

Here inorder traversal output is used to arrange the nodes as doubly linked list. And left link is used for prev pointer and right link is used for next pointer.

Just like in inorder traversal, we call the function with left child and right child. Between these two calls, instead of displaying the node, we link this node to previous node using
node->left = prevnode
prevnode->right = node

The node which has no previous node (NULL) is taken as head of of doubly linked list.

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

void convert_to_dll(NODEPTR nd,NODEPTR*headptr)
{
   static NODEPTR prevnode;
   if(nd!=NULL)
    {       
        convert_to_dll(nd->left,headptr);
        if(prevnode!=NULL){
           prevnode->right = nd;
           nd->left = prevnode;
        }
        else{
           *headptr = nd;
        }
        prevnode = nd; 
        convert_to_dll(nd->right,headptr);
     }
}
NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
} 
void print_dll(NODEPTR nd)
{
   NODEPTR temp = nd;
    while(nd)
      {
        printf("%d---->",nd->val);
        nd = nd->right;
       } 
} 

void inorder(NODEPTR nd)
{
   if(nd!=NULL)
   {	
      inorder(nd->left);
      printf("%d ",nd->val);
      inorder(nd->right);
    }
}

int main()
{
       NODEPTR root=NULL,delnode,head;  
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
        
       head = NULL;
       convert_to_dll(root ,&head);
       print_dll(head); 
       return 0;
}

23. Given a binary tree, write a function to determine whether it is a binary search tree

A binary search tree must follow the rule that each node has key values smaller than itself on its left subtree and key values larger than itself on its right subtree.

In an inorder traversal, these rules are tested. If the inorder traversal output is not in ascending order, then the tree is not a BST.

So previous output of recursive call is stored in a global variable and is compared each time. If the current value is less than previous output, then the binary tree is not a binary search tree

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;
static int prevValue;

int isBST(NODEPTR nd)
{ 
 if(nd!=NULL)
  {
     if(!isBST(nd->left))
       return 0;
     if(nd->val<prevValue)
       return 0;
     prevValue = nd->val;
     return isBST(nd->right);
  }
  else
    return 1;
}
NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
}
 
NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}
NODEPTR create_tree1()
{
        NODEPTR n1,n2,n3,n4,n5,n6,n7,root;
        n1 = create_node(10);
        n2 = create_node(20);
        n3 = create_node(30);
        n4 = create_node(40);
        n5 = create_node(50);
        n6 = create_node(60);
        n7 = create_node(70);
        root = n3;
        n3->left = n1;
        n1->right = n2;
        n3->right = n6;
        n6->left = n4;
        n4->right = n5;
        n6->right = n7;
        return root;
}
NODEPTR create_tree2()
{
        NODEPTR n1,n2,n3,n4,n5,n6,n7,root;
        n1 = create_node(10);
        n2 = create_node(20);
        n3 = create_node(30);
        n4 = create_node(40);
        n5 = create_node(50);
        n6 = create_node(60);
        n7 = create_node(70);
        root = n3;
        n3->left = n1;
        n1->left = n2;
        n3->right = n6;
        n6->left = n4;
        n4->right = n5;
        n6->right = n7;
        return root;
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d---",nd->val);
        in_order(nd->right);
     }
} 
int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       root = create_tree1();
       printf("\nInorder traversal\n");
       in_order(root);
       if(isBST(root))
          printf("The tree is a binary search tree");
       else
          printf("The tree is not a binary search tree");
       root =create_tree2();
      in_order(root);
       if(isBST(root))
          printf("this tree is a binary search tree");
       else
          printf("this tree is not a binary search tree");            
       return 0;
}

24. Determine whether an input array is a post-order traversal sequence of a binary tree or not. Assume all numbers in an input array are unique.

Travese the tree in post order. Instead of printing values, compare it with arr[index] and increment index.

If array element does not match with traversal output, then return false.

int is_array_post_order(NODEPTR nd,int *arr)
{
   static int index=0; 
   if(nd!=NULL)
    {
        int leftst,rightst;	
        leftst =  is_array_post_order(nd->left,arr);       
        rightst =  is_array_post_order(nd->right,arr); 
        if(arr[index++]!=nd->val)
            return 0; 
        if( leftst==0 || rightst==0)
       { 
		return 0;
       }
        else  return 1;
     }
     return 1;
}

25. Given a binary search tree and a value k, find a node in the binary search tree whose value is closest to k.

This algorithm uses binary search, but when traversing nodes checks if the difference between node value and search value is smaller than previous difference.

If yes, it stores the node value and the difference. This procedure is continued until a NULL is encountered

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d---",nd->val);
        in_order(nd->right);
     }
}

int absolute(int m)
{
   return m<0?-m:m;
}
int find_closest_num(NODEPTR nd,int num)
{
      int mindiff=absolute(nd->val - num);
      int closest_val=nd->val;
      while(nd!=NULL)
      {
          int d = absolute(num - nd->val);
          if( d<mindiff)
         {
              mindiff = d;
              closest_val = nd->val;
          } 
          if(num>nd->val)
              nd = nd->right;
          else if(num<nd->val)
              nd = nd->left;
          else	
              return nd->val;/*diff is 0*/
     }
     return closest_val;
}

int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
       
       printf("\nInorder traversal\n");
       in_order(root);
      
       while(1)
       {
          NODEPTR snode;
          int num1,num2;
          printf("Enter a number(-1 to stop):");
          scanf("%d",&num1);
          if(num1==-1)
             break;
          int a =find_closest_num(root,num1);          
          printf("closest value to %d is %d\n",num1,a);
       }
       return 0;
}

26. Write a function for breadth first traversal of a binary tree.

Breadth first traversal of a binary tree is the method of visiting all the nodes of a level first and then moving on to next level. ie. we visit the siblings of a node before we visit the children.

In BFS, we visit all nodes at level 0 (only one here), then visit all nodes at level 1 and then all nodes at level 2 and so on.

This algorithm requires you to use a queue along with a BST.

1) Enqueue the root of the tree
2) while queue is not empty repeat
a) dequeue a node from queue.
b) visit the node
c) enqueue the left and right child nodes of this node

For this tree
300
10 500
2 18 800

the output should be 300, 10, 500, 2, 18, 500

 #include<stdio.h>
#include<stdlib.h>
struct btnode
{ 
    int value; 
    struct btnode *left, *right; 
};
typedef struct btnode *NODEPTR ;
#define MAX 40
struct queue
{ 
   NODEPTR nodes[40];
   int rear,front;
}; 

 NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->value > nd->value)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->value <  nd->value)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}
 
NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct btnode));
     temp->value = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 
void enqueue(struct queue *qptr,NODEPTR newnode)
{
    if(qptr->rear>=MAX)
      {
        printf("Queue overflow");
        return;
      }
    qptr->rear++;
    qptr->nodes[qptr->rear]=newnode;
}
int is_empty(struct queue qptr)
{
    if (qptr.front>qptr.rear)
      return 1;
    return 0;
}
  
NODEPTR dequeue(struct queue *qptr)
{
    if(is_empty(*qptr))
    {
        printf("Queue empty");
        return NULL;
    }    
    NODEPTR temp= qptr->nodes[qptr->front];
    qptr->front++;
    return temp;
}  

/* displaying elements using BFS traversal */

void bfs_traverse(NODEPTR root)
{
    struct queue q1;
    NODEPTR nd;
    q1.front=0;q1.rear =-1;
    enqueue(&q1,root);
    while(!is_empty(q1))
    {
        nd = dequeue(&q1) ;
        if(nd==NULL)
          break;
        printf("%d  ",nd->value);    	
        if (nd->left != NULL)
            enqueue(&q1,nd->left);
        if (nd->right != NULL )
            enqueue(&q1,nd->right);         
    }     
}
int main() 
{ 
    NODEPTR root = NULL,newnode ; 
    int num = 1; 
    printf("Enter the elements of the tree(enter -1 to exit)\n"); 

    while (1) 
    {     
        scanf("%d",  &num); 
        if (num  ==  -1) 
            break; 
        newnode = create_node(num);
        root = insert_node(root,newnode);
    }

    printf("elements in bfs are\n"); 
    bfs_traverse(root);
    
}

27. Write a function for depth first traversal of a binary tree

DFS traversal of a binary tree is nothing is the traversal method where you go deep into the tree before visiting siblings.

The three methods of Depth first traversals are inorder, preorder and postorder

28. Write a program to print kth smallest element of a binary search tree

int kth_smallest(NODEPTR nd,int k )
{
   static int m=0;  
   if(nd!=NULL)
    {
        int a =  kth_smallest(nd->left,k );
        m++;
        if(m==k)
           return nd->val;
        int b= kth_smallest(nd->right,k);
        return a;
     }
}
 

int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
       
       printf("\nInorder traversal\n");
       in_order(root);
      
       printf("Enter k:");
       scanf("%d",&n);
       int smallest=
       kth_smallest(root,n);
       printf("%dth smallest element is %d\n",n,smallest);
       return 0;
}
/*compile this with binary tree library*/

29. Write a program to merge two binary search trees

To merge two binary search trees, you can use the following method.

Convert 2nd tree to a doubly linked list
Remove one node from this list at a time
Set the child links of this node to NULL
Insert this node into 1st tree
Repeat this until all nodes of list are removed and added to tree.

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
    return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
     nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
     nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void convert_to_dll(NODEPTR nd,NODEPTR*headptr)
{
   static NODEPTR prevnode;
   if(nd!=NULL)
    {    
    convert_to_dll(nd->left,headptr);
     if(prevnode!=NULL){
        prevnode->right = nd;
        nd->left = prevnode;
     }
     else{
        *headptr = nd;
     }
     prevnode = nd; 
     convert_to_dll(nd->right,headptr);
     }
}
 
NODEPTR merge_bsts(NODEPTR root,NODEPTR root2)
{
     NODEPTR head = NULL;
     convert_to_dll(root2,&head);
     while(head!=NULL)
     {
	NODEPTR temp = head;
	head = head->right;
                 temp->left = temp->right = NULL;/*detach from list*/
	root = insert_node(root,temp);/*insert into first tree*/
      }
      return root;
}

void inorder(NODEPTR nd)
{
   if(nd!=NULL)
   {	
	inorder(nd->left);
	printf("%d ",nd->val);
                inorder(nd->right);
    }
}

int main()
{
    NODEPTR root=NULL,delnode,head; 
    NODEPTR root2 = NULL;
    int n;
    do
    {
        NODEPTR newnode;
        printf("Enter value of node(-1 to exit):");
        scanf("%d",&n);
        if(n!=-1)
         {  
         newnode = create_node(n);
         root = insert_node(root,newnode);
          }
    } while (n!=-1);
    printf("Second bst:");
    do
    {
        NODEPTR newnode;
        printf("Enter value of node(-1 to exit):");
        scanf("%d",&n);
        if(n!=-1)
         {  
         newnode = create_node(n);
         root2 = insert_node(root2,newnode);
          }
    } while (n!=-1);
    head = NULL; 
    root  = merge_bsts(root,root2); 
    printf("Merged bst is ");
    inorder(root);
    return 0;
}

30. Find the sum of all elements in level k of a binary search tree

One method would be to write level order traversal (BFS) and then add elements of kth level. But remember that level order traversal needs a queue also.

Another method is we write a recursive function where we traverse the tree inorder until we reach level k. For all nodes with level k we return a value of that node. For higher levels we return the level sum of left subtree+ level sum of right subtree .

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

int sum_at_levelk(NODEPTR nd,int level,int k)
{   
   if(nd==NULL)
      return 0;
   if(level<k) 
      {
       int a = sum_at_levelk(nd->left,level+1,k);
       int b = sum_at_levelk(nd->right,level+1,k);
      return a+b;
    } 
   if(level==k)
   { 
      return nd->val;
   }
}

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
       nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
       nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
     in_order(nd->left);
     printf("%d---",nd->val);
     in_order(nd->right);
     }
}
   
int main()
{
    NODEPTR root=NULL,delnode; 
    int n,k;
    do
    {
        NODEPTR newnode;
        printf("Enter value of node(-1 to exit):");
        scanf("%d",&n);
        if(n!=-1)
         {  
         newnode = create_node(n);
         root = insert_node(root,newnode);
          }
    } while (n!=-1);
    
    printf("\nInorder traversal\n");
    in_order(root);
    while(1)
    {
       printf("Enter level (-1 to exit):");
        scanf("%d",&k);
       if(k==-1)
          break;
        printf("Sum of elements at level %d is %d \n",k,sum_at_levelk(root,0,k));
    } 
    return 0;
}

31. Write a function to find the lowest common ancestor of two given nodes in a binary search tree

If you search for both the numbers and as long as both the numbers are on the same path from root, they have common ancestors.

The node where they branch out in search path is the lowest common ancestor.

200
100 500
10 170 800

LCA of 10 and 170 is 100
LCA of 10 and 800 is 200
LCA of 10 and 200 is 200
LCA of 500 and 100 is 200

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR lowest_common_ancestor(NODEPTR root, int num1,int num2)
{
   NODEPTR temp = root;
   while(temp!=NULL)
   {
        if(num1>temp->val && num2>temp->val ) 
              temp = temp->right; 
        else if(num1<temp->val && num2<temp->val)
              temp= temp->left;
        else
              break; 
    }
    return temp;  
} 
NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
       return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
        nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
        nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
        in_order(nd->left);
        printf("%d---",nd->val);
        in_order(nd->right);
     }
} 

int main()
{
       NODEPTR root=NULL,delnode; 
       int n;
       do
       {
           NODEPTR newnode;
           printf("Enter value of node(-1 to exit):");
           scanf("%d",&n);
           if(n!=-1)
            {  
               newnode = create_node(n);
               root = insert_node(root,newnode);
             }
       } while (n!=-1);
       
       printf("\nInorder traversal\n");
       in_order(root);
      
       while(1)
       {
          NODEPTR snode;
          int num1,num2;
          printf("Enter two values num1 and num2:");
          scanf("%d %d",&num1,&num2);
          snode = lowest_common_ancestor(root,num1,num2);
          if(snode==NULL)
             printf("Value not found");
          else 
             printf("ancestor is %d\n",snode->val);
       }
       return 0;
}

32. Write a function to convert a binary tree into its mirror that is for each node, its left subtree and right subtree must be swapped.

To get mirror of a binary tree, we have to swap left and right child links of all the nodes recursively.

If binary tree is

32
10 900
2

Then its mirror is
32
900 10
2

In order traversal of mirror of a binary search tree gives key values in descending order.

void mirror_tree(NODEPTR root)
{
   if(root!=NULL)
   {
         NODEPTR temp = root->left;
         root->left = root->right;
         root->right = temp;
         mirror_tree(root->left);
         mirror_tree(root->right);
    }
}

33. Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.

Here we traverse recursively both the trees parallely. We compare the values. If the values are not matching or if one of them is NULL when other node is not, the trees are unequal.

#include<stdio.h>
#include<stdlib.h>
struct node
{
   int val;
   struct node *left;
   struct node *right;
};
typedef struct node *NODEPTR;

NODEPTR create_node(int num)
{
     NODEPTR temp = (NODEPTR)malloc(sizeof(struct node));
     temp->val = num;
     temp->left = NULL;
     temp->right = NULL;
     return temp;
} 

NODEPTR insert_node(NODEPTR nd,NODEPTR newnode)
{
    if(nd==NULL)
    return newnode;/* newnode becomes root of tree*/
    if(newnode->val > nd->val)
     nd->right = insert_node(nd->right,newnode);
    else if(newnode->val <  nd->val)
     nd->left = insert_node(nd->left,newnode); 
    return nd;   
}

void in_order(NODEPTR nd)
{
   if(nd!=NULL)
    {
     in_order(nd->left);
     printf("%d---",nd->val);
     in_order(nd->right);
     }
}
int equal_trees(NODEPTR nd1,NODEPTR nd2)
{
    if(nd1==nd2)
    return 1;/*both are null*/
    if(nd1==NULL || nd2==NULL )     
      return 0;/*either but not both*/
    if(nd1->val!=nd2->val)
      return 0;
      else
    {
      int l= equal_trees(nd1->left,nd2->left);
      int r = equal_trees(nd1->right,nd2->right);
      return l&r;
    }
}    
      
NODEPTR create_tree()
{
    NODEPTR root = NULL;
    int n;
    do
    {
        NODEPTR newnode;
        printf("Enter value of node(-1 to exit):");
        scanf("%d",&n);
        if(n!=-1)
         {  
      newnode = create_node(n);
         root = insert_node(root,newnode);
          }
    } while (n!=-1);
     return root;
}
 

int main()
{
    NODEPTR root=NULL,delnode; 
    int n;
    NODEPTR root1,root2;
    printf("First tree:");
    root1 = create_tree();
    in_order(root1);
    printf("Second tree:");
    root2 = create_tree();
    in_order(root2);
    if(equal_trees(root1,root2))
       printf("The two tree are equal");
    else
       printf("The two trees are not equal"); 
    
}

34. Write a function to display the numbers in order of a binary search tree in the range x to y. Hint on the analysis: the visited nodes are found to the right of one path in the tree and to the left of another.

This is similar to in-order traversal. But if a node has a value less than x, then you need not visit its left sub-tree. Similarly, for nodes with value greater than y, you do not call recursive function on right subtree.

void in_order_middle(NODEPTR nd,int x, int y)
{
    if(nd  )
    { 
        if(nd->val >=x)
             in_order_middle(nd->left,x,y);
        if(nd->val>=x && nd->val<=y)
	    printf("%d  ",nd->val);
        if(nd->val <=y)
           in_order_middle(nd->right,x,y); 
    }
}

BinaryTree Questions