Print Nodes of Binary Tree Level Wise

Write a C program to perform level order traversal of a binary tree.
How to print nodes of a binary tree at same level in one line.

Given a binary tree, we have to traverse it using level order traversal. In Level order traversal we first traverse all nodes at level L from left to right then only we can traverse nodes at level L + 1. Level order traversal is also known as breadth first search.
We can perform level order traversal either using recursion or using queue data structure. Here we will discuss about both approaches of breadth first search.

Method 1 : Using a recursive function to print one level at a time

In this approach, we will use two functions :

printNodesAtLevel : This function prints all nodes at a particular level L, from left to right.
levelOrderTraversal : This function call printNodesAtLevel function multiple times to print nodes at each level of binary tree.

Algorithm to print nodes at given level
Let "node" be the pointer to any node of binary tree and we want to print all nodes at level L.
We will do pre order traversal of given binary tree and keep track of the level of current node. If level of current node is equal to L then we will print it on screen else continue pre order traversal.

If node is equal to NULL, return.
If level of node is equal to L, then print node and return.
Recursively traverse left and right sub trees at level L + 1.

Time Complexity : O(N²) where N is the number of nodes in binary tree. printNodesAtLevel takes O(N) time to print nodes of a single level. As we are printing nodes of L levels we will call printNodesAtLevel L times. In worst case when binary tree is a skewed tree L is equal to N. Hence worst case time complexity will be O(N²)

C program to print level order traversal of binary tree

#include <stdio.h>

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

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         2    3
        / \    \
       4  5    7
      / \
     8  9
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);

    root->left = getNewNode(2);
    root->right = getNewNode(3);

    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->right = getNewNode(7);
 
    root->left->left->left = getNewNode(8);
    root->left->left->right = getNewNode(9);
    
    return root;
}

/* Returns maximum of two given numbers */
int getMax(int a, int b){
    if(a >= b)
        return a;
    else 
        return b;
}
/*
Returns height of a bianry tree
*/
int getHeight(struct node *root){
    int leftHeight, rightHeight;
    if(root == NULL)
        return 0;
    leftHeight = getHeight(root->left);
    rightHeight = getHeight(root->right);
    
    return getMax(leftHeight, rightHeight) + 1;
}
/* 
   Prints all node at a particular level. It does pre Order 
   traversal and keeps track of the current level.
   If current level is equal to the level, it prints current node
*/
void printNodesAtLevel(struct node* root, int currentLevel, int level) {
  
  if(root == NULL) {
      return;   
  }  
  if(currentLevel == level) {
      printf(" %d ", root->data);
      return;
  }
             
  printNodesAtLevel(root->left, currentLevel+1, level);
  printNodesAtLevel(root->right, currentLevel+1, level);
}

/* Printd nodes of binary tree level wise */
void levelOrderTraversal(struct node* root){
    /* Find the height of tree */
    int i, height = getHeight(root);
    /* Iterate from level 0 to height-1 and 
 print one level at a time */
    for(i = 0; i < height; i++){
     printNodesAtLevel(root, 0, i);
     printf("\n");
    }
}

int main() {
    struct node *root = generateBTree();    
    
    /*Printing all nodes level wise*/
    levelOrderTraversal(root);
    
    getchar();
    return 0; 
}

Output