Find Max/Min Value in a Binary Tree (Not a Binary search tree)

//
//Recursive Max Value function
 int max_rec (Node *root)
{
    int left,right;   

    //Base Case
    if (root == NULL)
        return -1;

    left = max_rec(root->left);
    right = max_rec(root->right);

    return max (left , right , root->data) ;
}

//
//Iterative or Non Recursive Max using BFS Traversal
//

 int max_iter (Node *root)
{
    Node *temp = NULL;
    int tmp = -1 ;

    //if tree is null return
    if (!root)
        return 0;

    //Create a Queue and push root
    Que *Q = CreateQue();
    enQue(Q,root);

    //Loop while Queue is not empty
    while (!isEmpty(Q))
    {
        temp = deQue(Q);
        //check min data and save 
        if(tmp<temp->data)
            tmp = temp->data;
        if(temp->left)
            enQue(Q,temp->left);
        if(temp->right)
            enQue(Q,temp->right);
    }
    return tmp;
}

Depth/Height of a Binary Tree ( Recursive and Iterative versions )

Algorithm For Recursion : 

1. If tree is empty then return 0

2. Else

     (a) Get the max depth of left subtree recursively  i.e.,

          call maxDepth( tree->left-subtree)

     (a) Get the max depth of right subtree recursively  i.e.,

          call maxDepth( tree->right-subtree)

     (c) Get the max of max depths of left and right

          subtrees and add 1 to it for the current node.

         max_depth = max(max dept of left subtree, 

                             max depth of right subtree)

                             + 1

     (d) Return max_depth

 int depth_rec (Node *root)
{
    if (root == NULL)
        return 0;

    int left , right ;
    left = depth_rec(root->left);
    right = depth_rec(root->right);

    if(left > right)
        return (left+1);
    else
        return (right+1);
} 

How to find height without recursion?

We can use level order traversal to find height without recursion.
 The idea is to traverse level by level.  Whenever move down to a level, increment height by 1
 (height is initialized as 0). 
Count number of nodes at each level, stop traversing when count of nodes at next level is 0. Following is detailed algorithm to find level order traversal using queue.

Create a queue.
Push root into the queue.height = 0
Loop        
 nodeCount = size of queue                
// If number of nodes at this level is 0,
return height        
 if nodeCount is 0               
 return Height;        
 else              
increase Height         
 // Remove nodes of this level and add nodes of         
 // next level       
while (nodeCount > 0)              
pop node from front               
 push its children to queue               
 decrease nodeCount      
 // At this point, queue has nodes of next level

 int depth_iter (Node *root)
{
    Node *temp = NULL;
    int depth =0 ;
    int node_cnt =0 ;

    //Base case
    //if tree is null return
    if (!root)
        return 0;

    //Create a Queue and push root
    Que *Q = CreateQue();
    enQue(Q,root);

    while(1)
    {
         // nodeCount (queue size) indicates number of nodes
         // at current lelvel.
        node_cnt = sizeQue(Q);
        if (node_cnt == 0)
            return depth;
            
        //as nodes are not zero means one more level is there
        depth++;

        // Dequeue all nodes of current level and Enqueue all
        // nodes of next level
    while (node_cnt > 0) {
        temp = deQue(Q);
        if(temp->left)
            enQue(Q,temp->left);
        if(temp->right)
            enQue(Q,temp->right);
        node_cnt--;
        }
    }
}

Breadth First Traversal and Size of Tree (Non Recursive version)

typedef struct que {
    int front;
    int rear;
    Node **array;
}Que;

 Que * CreateQue(void)
{
    Que * temp = (Que *) malloc (sizeof(Que));
    temp->front = -1;
    temp->rear = -1;
    temp->array = (Node **) malloc (SIZE * sizeof (Node *));
    return temp;
}

void  enQue (Que *que, Node *temp )
{
    // Generally for Que for a EnQUe op
    // only rear gets changed. (added at end)
    //
    // this is a array which we wnat to manage
    // as a circular array
    que->rear = (que->rear + 1) % SIZE;
    que->array[que->rear] = temp;

    if(que->front == -1)
        que->front = que->rear;
}
 Node * deQue (Que *que)
{
    Node *temp = que->array[que->front];

    if (que->front == que->rear) {
        que->front =-1;
        que->rear = -1;
    }
    else
      que->front = (que->front+1) % SIZE;
    return temp;
}

 int isEmpty (Que *que)
{
    return (que->rear == -1);
}

//Non Recursive Size using BFS Traversal
 int bfs_size (Node *root)
{
    Node *temp = NULL;
    int count =0 ;

    //if tree is null return
    if (!root)
        return 0;

    //Create a Queue and push root
    Que *Q = CreateQue();
    enQue(Q,root);

    //Loop while Queue is not empty
    while (!isEmpty(Q))
    {
        temp = deQue(Q);
        printf(" %d ",temp->data);
        count++;
        if(temp->left)
            enQue(Q,temp->left);
        if(temp->right)
            enQue(Q,temp->right);
    }
    return count;
}

int main ()
{
    Node *root = addNode(1);
    root->left = addNode(2);
    root->right = addNode(3);
    root->left->left  = addNode(5);
    printf("size of binary tree is %d\n",bfs_size(root));
    return 0;
}

Size of a Binary Tree

Write a Program to find Size of a Binary Tree

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int data;
    struct node* left;
    struct node* right;
} Node;

 Node * addNode (int data)
{
    Node *temp = (Node *) malloc (sizeof (Node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

 int size (Node *root)
{
    if (root == NULL)
        return 0;
    return (size(root->left) + size(root->right) + 1);
}

int main ()
{
    Node *root = addNode(1);
    root->left = addNode(2);
    root->right = addNode(3);
    root->left->left  = addNode(5);
    printf("size of binary tree is %d\n",size(root));
    return 0;
}

Design a Queue using Linked List

Structures for Queue Data Strucuture

//
// Queue Data Structure
// 

typedef struct node
{
    int data;
    struct node *next;
}Node;

typedef struct
{
    Node *front,*rear;
    int count;
    int size;
}Que;

Methods 

Node * createNode (int data)
{
    Node *temp = (Node *) malloc (sizeof(Node));
    if (!temp){
        printf("\nerror malloc\n");
            temp = NULL;
    }
    else {
        temp->data = data;
        temp->next = NULL;
    }
        return temp;
}

int isFull (Que *q)
{
    if (q)
    return (q->size == q->count);
}

int isEmpty (Que *q)
{
    if (q)
    return (q->front == NULL);
}

void enQue (Que *q, int data)
{
    printf ("adding %d\n",data);
    Node *temp = NULL;
    if (isFull(q)){
        printf("\nQue Full\n");
        return ;
    }
    temp = createNode(data);
    if(q->rear){
        q->rear->next = temp;
        q->rear = temp;
    }
    else {
        q->rear = temp;
        q->front = temp;
    }
}

int deQue (Que *q)
{
    int ret = -1;
    Node *temp = NULL;
    if (isEmpty(q))
        printf("\nEmpty Q\n");
    else {
        temp = q->front;
        ret = temp->data;
        q->front = q->front->next;
        free(temp);
    if (!q->front)
        q->rear = q->front;
    }
return ret;
}