Tree Traversals-II [BT]

Question 1:Discuss breadth first traversal or Level order traversal of a binary tree.Also show how we can search in breadth first search
http://www.geeksforgeeks.org/level-order-tree-traversal/
http://mhesham.wordpress.com/tag/bfs-vs-dfs/

Question 2:Print a binary tree level by level with each level printed on a new line.

Input Tree:
           6
         /    \
       4      8
     /   \       \
    1    5      9

Output:
6
4 8
1 5 9
http://quiz.geeksforgeeks.org/print-level-order-traversal-line-line/

Question 3:Also print the level order data in reverse order. ie for below tree function should print

7654
23
1
http://www.geeksforgeeks.org/reverse-level-order-traversal/

Question 4:Level order traversal in spiral form
Write a function to print spiral order traversal of a tree. For below tree, function should print 1, 2, 3, 4, 5, 6, 7. 
                                                      1
                                                   /      \
                                                2         3
                                             /     \     /     \
                                           7     6   5      4
http://www.geeksforgeeks.org/level-order-traversal-in-spiral-form/
http://articles.leetcode.com/printing-binary-tree-in-zig-zag-level_18/

Question 5:Given a Binary Tree and a key, write a function that returns level of the key.
For example, consider the following tree. If the input key is 3, then your function should return 1. If the input key is 4, then your function should return 3. And for key which is not present in key, then your function should return 0.

Question 6:
Given a root of a tree, and an integer k. Print all the nodes which are at k distance from root.
For example, in the below tree, 4, 5 & 8 are at distance 2 from root.

1
          /   \
        2      3
      /  \    /
    4     5  8

Question 7:
Wap to do a level order sum of a binary tree
Question 8:
Calculate the difference between the sum of nodes at even level and sum of nodes at odd level.
Question 9:
Print the level of the binary tree which has the maximum number of nodes.
http://www.dsalgo.com/2013/03/binary-tree-level-with-maximum-number.html
Question 10:
http://www.geeksforgeeks.org/perfect-binary-tree-specific-level-order-traversal/
http://www.geeksforgeeks.org/perfect-binary-tree-specific-level-order-traversal-set-2/

Level Order Traversal--------------

Method 1:Using DFS

void printLevelOrder(struct node* root)

{

  int h = height(root);

  int i;

  for(i=1; i<=h; i++)

    printGivenLevel(root, i);

}    

void printGivenLevel(struct node* root, int level)

{

  if(root == NULL)

    return;

  if(level == 1)

    printf("%d ", root->data);

  else if (level > 1)

  {

    printGivenLevel(root->left, level-1);

    printGivenLevel(root->right, level-1);

  }

}

int height(struct node* node)

{

   if (node==NULL)

       return 0;

   else

   {

     /* compute the height of each subtree */

     int lheight = height(node->left);

     int rheight = height(node->right);

     /* use the larger one */

     if (lheight > rheight)

         return(lheight+1);

     else return(rheight+1);

   }

}

Time Complexity: O(n^2) in worst case. For a skewed tree, printGivenLevel() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n^2).

Argument for O(n) Complexity:
http://www.leetcode.com/2010/09/binary-tree-level-order-traversal-using_17.html



Method 2:Using Queue 

For each node, first the node is visited and then it’s child nodes are put in a FIFO queue.



#include <stdio.h>
#include <stdlib.h>
#define MAX_Q_SIZE 500

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

struct node** createQueue(int *front, int *rear)
{
  struct node **queue =
   (struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE);

  *front = *rear = 0;
  return queue;
}

void enQueue(struct node **queue, int *rear, struct node *new_node)
{
  queue[*rear] = new_node;
  (*rear)++;
} 

struct node *deQueue(struct node **queue, int *front)
{
  (*front)++;
  return queue[*front - 1];
} 

struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;

  return(node);
}

void printLevelOrder(struct node* root)
{
  int rear, front;
  struct node **queue = createQueue(&front, &rear);
  struct node *temp_node = root;

  while(temp_node)
  {
    printf("%d ", temp_node->data);

    if(temp_node->left)
      enQueue(queue, &rear, temp_node->left);

    if(temp_node->right)
      enQueue(queue, &rear, temp_node->right);

    temp_node = deQueue(queue, &front);
  }
}

int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);

  printf("Level Order traversal of binary tree is \n");
  printLevelOrder(root);

  getchar();
  return 0;
}

Time Complexity: O(n) where n is number of nodes in the binary tree

Alternatively,

void bfs(struct node* root)
{
    queue q;

    q.push(root);

    while(!q.empty())
    {
        struct node* temp = q.front();
        q.pop();
        
        printf("%d ", temp->data);

        if(temp->left != NULL)
            q.push(temp->left);

        if(temp->right != NULL)
            q.push(temp->right);
    }
    printf("\n");
}

Print Each level in new line:

Using BFS:
The regular BFS algorithm doesn't keep a track of the level it is on. We

will modify it to segregate the levels with a NULL value to keep track of the current level. Below is the code,

void printLevel(struct node* root)
{
    queue q;
    q.push(root);
    q.push(NULL);

    while(q.front() != NULL)
    {
        struct node* temp = q.front();
        q.pop();

        while(temp != NULL)
        {
            printf("%d ", temp->data);

            if(temp->left != NULL)
                q.push(temp->left);

            if(temp->right != NULL)
                q.push(temp->right);

            temp = q.front();
            q.pop();
        }
        printf("\n");
        q.push(NULL);
    }
}

Alternatively,

In order to print the binary tree in level order with newline in the end of each level, we can utilize two queues. The first queue stores the current level’s nodes, while the second queue stores the next level’s nodes (the current level nodes’ children).

When the first queue is emptied, we know that it must have reached the end of the current level, therefore we print a newline. Then, we switch the emptied first queue with the second queue (which is populated with the next level’s nodes). Then we repeat the process over again.

void printLevelOrder(BinaryTree *root) {
  if (!root) return;
  queue<BinaryTree*> currentLevel, nextLevel;
  currentLevel.push(root);
  while (!currentLevel.empty()) {
    BinaryTree *currNode = currentLevel.front();
    currentLevel.pop();
    if (currNode) {
      cout << currNode->data << " ";
      nextLevel.push(currNode->left);
      nextLevel.push(currNode->right);
    }
    if (currentLevel.empty()) {
      cout << endl;
      swap(currentLevel, nextLevel);
    }
  }
}

Alternatively,

We can use a single queue & keep two variables to keep track of nodes in current level and next level as follows: When we pop a node off the queue, we decrement nodesInCurrentLevelby one. When we push its child nodes to the queue, we increment nodesInNextLevel by two. WhennodesInCurrentLevel reaches 0, we know that the current level has ended, therefore we print an endline here.

void printLevelOrder(BinaryTree *root) {
  if (!root) return;
  queue<BinaryTree*> nodesQueue;
  int nodesInCurrentLevel = 1;
  int nodesInNextLevel = 0;
  nodesQueue.push(root);
  while (!nodesQueue.empty()) {
    BinaryTree *currNode = nodesQueue.front();
    nodesQueue.pop();
    nodesInCurrentLevel--;
    if (currNode) {
      cout << currNode->data << " ";
      nodesQueue.push(currNode->left);
      nodesQueue.push(currNode->right);
      nodesInNextLevel += 2;
    }
    if (nodesInCurrentLevel == 0) {
      cout << endl;
      nodesInCurrentLevel = nodesInNextLevel;
      nodesInNextLevel = 0;
    }
  }
}

Using DFS:

void printLevelOrder(struct node* root)
{
  int h = height(root);
  int i;
  for(i=1; i<=h; i++)
    {printGivenLevel(root, i);
    printf("\n");}
}  


Level Order Traversal in Spiral form




To print the nodes in spiral order, nodes at different levels should be printed in alternating order. An additional Boolean variable ltr is used to change printing order of levels. If ltr is 1 then printGivenLevel() prints nodes from left to right else from right to left. Value of ltr is flipped in each iteration to change the order.

void printLevelOrder(struct node* root)

{

  int h = height(root);

  int i;

  /*ltr is set then the given level is traverseed from left to right. */

  bool ltr = 0;

  for(i=1; i<=h; i++)

  {

    printGivenLevel(root, i, ltr);

    ltr = ~ltr;//Revert ltr to traverse next level in oppposite order

  }

}   

void printGivenLevel(struct node* root, int level, int ltr)

{

  if(root == NULL)

    return;

  if(level == 1)

    printf("%d ", root->data);

  else if (level > 1)

  {

    if(ltr)

    {

      printGivenLevel(root->left, level-1, ltr);

      printGivenLevel(root->right, level-1, ltr);

    }

    else

    {

      printGivenLevel(root->right, level-1, ltr);

      printGivenLevel(root->left, level-1, ltr);

    }

  }

}
Alternatively:We have to use two stacks for doing this operation

• At every level, we will push the nodes in one stack and print them.
• At every push, print the node.
• At every pop, push the children in another stack.
• When the stack is empty change the traversal direction. i.e. if its left and then right node, it will be changed as right and then left node.

Level order Traversal in reverse order

 void printLevelOrder(struct node* root)
{
  int h = height(root);
  int i;
  for(i=h; i>=1; i--)
    {printGivenLevel(root, i);
    printf("\n");}
}  

Getting Level of a node

start from the root and level as 1. If the key matches with root’s data, 

return level.  Else recursively call for left and right subtrees with 
level as level + 1. 

int getLevelUtil(struct node *node, int data, int level)

{

  if ( node == NULL )

    return 0;

  if ( node->data == data )

    return level;

  return getLevelUtil ( node->left, data, level+1) |

         getLevelUtil ( node->right, data, level+1);

}

int getLevel(struct node *node, int data)

{

  return getLevelUtil(node,data,1);

}

Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.

Level Wise Sum of Binary Tree:

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

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


int height(struct node* node)
{
if (node==NULL)
return 0;
else
{

int lheight = height(node->left);
int rheight = height(node->right);


if (lheight > rheight)
return(lheight+1);
else return(rheight+1);
}
}


int printGivenLevel(struct node* root, int level)
{
if(root == NULL)
return 0;
if(level == 1)
{
return root->data;
}
else if (level > 1)
{
return (printGivenLevel(root->left, level-1)+ printGivenLevel(root->right, level-1));
}
}

void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for(i=1; i<=h; i++)
printf(" %d \t ",printGivenLevel(root, i));
}

struct node* newNode(int data)
{
struct node* node = (struct node*)
malloc(sizeof(struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int main()
{
struct node *root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(4);
root->right->right = newNode(5);

printf("Level Order Sum of binary tree is \n");
printLevelOrder(root);

getchar();
return 0;
}

Print Nodes at k distance:

void printKDistant(node *root , int k)

{

   if(root == NULL)

      return;

   if( k == 0 )

   {

      printf( "%d ", root->data );

      return ;

   }

   else

   {

      printKDistant( root->left, k-1 ) ;

      printKDistant( root->right, k-1 ) ;

   }

}

Searching:

struct node* BreadthFirstSearch(struct node *root, int searchValue)
{int front,rear;
  struct node **queue = createQueue(&front, &rear);
    struct node * currentNode=root;

    while(currentNode!=NULL)
    { if(currentNode->data == searchValue)
            return currentNode;

      if(currentNode->left)          
          enQueue(queue, &rear, currentNode->left);
      if(currentNode->right) 
          enQueue(queue, &rear, currentNode->right);

      currentNode = deQueue(queue, &front);
    }

    return NULL; 
}

int main()
{
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);
  root->left->right->left = newNode(6);
  struct node* temp=BreadthFirstSearch(root, 6);
  if(temp!=NULL)
   printf("%d",temp->data);
  else
  printf("The searched value is not present");

  getchar();
  return 0;
}

Question 8:

Recursion is the easiest way to solve this problem. At each non-null 
node of the tree, we have three things to do. 1) Find the difference 
between the node's left child with it's children by calling the function
 recursively on the node's left child. 2) Do the same thing for the 
node's right child. 3) Find the difference between the current node and 
the sum of it's left and right child.