Print a binary tree from top to bottom in level order

Question

Given binary tree is:

        1
     /     \
    2        3
  /  \        \
 4   5         6
             /   \
            7     8

The output should be 1, 2, 3, 4, 5, 6, 7, 8

Answer 1

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

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

struct node *createnode(int k)
{
  struct node *nwnode=malloc(sizeof(struct node));
  nwnode->data=k;
  nwnode->left=NULL;
  nwnode->right=NULL;
  return nwnode;
}

void PrintLevelNodeBottomUp(struct node *t)
{
    if(t==NULL)
       return;
    struct node *List[20];
    int m;
    for(m=0;m<20;m++)
       List[m]=NULL;
        int i=0;
        int j=0;
    List[i++]=t;
    struct node *pP=List[0];
    List[i++]=createnode(-1);
    while(pP!=NULL && List[j+1]!=NULL)
    {
        if(pP->right!=NULL && pP->data!=-1)
           List[i++]=pP->right;
        if(pP->left!=NULL && pP->data!=-1)
           List[i++]=pP->left;
        if(pP->data==-1)
           List[i++]=createnode(-1);
        pP=List[++j];
    }
    for(m=i-1;m>=0;m--)
    {
      if(List[m]->data==-1)
         printf("\n");
          else
        printf("%d ",List[m]->data);
    }
}

int main(int args,char *argv[])
{
  root=createnode(11);
  root->left=createnode(4);
  root->right=createnode(15);  
  root->left->left=createnode(3);
  root->left->right=createnode(8);
  root->left->left->left=createnode(7);
  root->left->left->left->left=createnode(1);
  root->right->left=createnode(10);
  root->right->right=createnode(16);
  root->right->right->right=createnode(14);
  root->right->left->left=createnode(5);
  root->right->right->right->right=createnode(2);
  PrintLevelNodeBottomUp(root);
}

It will take 0(n) time and O(nlogn) space , I am sure there is much better solution possible.

Answer 2

I have used queue for Level order traversal and implemented it by using STL. "createBinaryTree" function will create a Binary tree until 0 is taken as the input that is, in my solution 0 can't be the input,we can change it according to our requirement. in function levelOrderTraversal, i have created a queue that will hold the current node and print it's data and then enqueue the right and left child of current node and dequeue the current node. for above tree, 1 is going to print first, then left and right child of 1 which is 2 and 3 is enqueued, now 2 is current node in the queue so 2 is going to be printed and child of 2 , 4 and 5 is enqueued and it continued in this way

#include<iostream>
#include<queue>
#include<stdlib.h>
using namespace std;

struct node{
    int data;
    struct node *left;
    struct node *right;
};
struct node *root=NULL;
int count1=1;

struct node *createBinaryTree(struct node *root,int data){

    if(root==NULL){
        root=(struct node *) malloc(sizeof(struct node));
        root->right=root->left=NULL;
        root->data=data;
    }
    else{
       if(count1%2!=0)
         root->left=createBinaryTree(root->left,data);
       else
        root->right=createBinaryTree(root->right,data);
    }
    return root;
  }

void levelOrderTraversal(struct node *root){
    struct node *tmp;
    if(root==NULL)
        return;
    queue <struct node *> myqueue; //creating a queue that will hold the address of nodes
    myqueue.push(root);            //pushing the root of the tree
    while(!myqueue.empty()){
        tmp=myqueue.front();      // tmp will hold the address of the current node
        cout <<' '<< tmp->data;
        myqueue.pop();
        if(tmp->left!=NULL)
            myqueue.push(tmp->left);   //left address of current node is inserted in queue
        if(tmp->right!=NULL)
            myqueue.push(tmp->right);  //right address of current node is inserted in queue
    }
}

int main(){
    int data;
    cin >> data;
    while(data!=0){
        root=createBinaryTree(root,data);
        cin >>data;
    }
    levelOrderTraversal(root);
    return 0;
}

Time complexity is O(n) and space complexity is O(n).

Comments

better explained @shashikant i have used the same method to solve level order traversal related questions.