Level Order Tree Traversal

Level Order Tree Traversal

METHOD 1 (Use function to print a given level)

Algorithm:

/*Function to print level order traversal of tree*/
printLevelorder(tree)
for d = 1 to height(tree)
   printGivenLevel(tree, d);

/*Function to print all nodes at a given level*/
printGivenLevel(tree, level)
if tree is NULL then return;
if level is 1, then
    print(tree->data);
else if level greater than 1, then
    printGivenLevel(tree->left, level-1);
    printGivenLevel(tree->right, level-1);

Time complexity : O(n^2)

c/c++ code:-

struct node

{

    int data;

    struct node* left, *right;

};

/* Function protoypes */

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

int height(struct node* node);

struct node* newNode(int data);

/* Function to print level order traversal a tree*/

void printLevelOrder(struct node* root)

{

    int h = height(root);

    int i;

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

        printGivenLevel(root, i);

}

/* Print nodes at a given level */

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);

    }

}

/* Compute the "height" of a tree -- the number of

    nodes along the longest path from the root node

    down to the farthest leaf node.*/

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);

    }

}

/* Helper function that allocates a new node with the

   given data and NULL left and right pointers. */

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);

}

/* Driver program to test above functions*/

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);

    return 0;

}

METHOD 2 (Use Queue)

Algorithm:

printLevelorder(tree)
1) Create an empty queue q
2) temp_node = root /*start from root*/
3) Loop while temp_node is not NULL
    a) print temp_node->data.
    b) Enqueue temp_node’s children (first left then right children) to q
    c) Dequeue a node from q and assign it’s value to temp_node

Time complexity : O(n)

 

C/C++ code:- 

struct node

{

    int data;

    struct node* left;

    struct node* right;

};

/* frunction prototypes */

struct node** createQueue(int *, int *);

void enQueue(struct node **, int *, struct node *);

struct node *deQueue(struct node **, int *);

/* Given a binary tree, print its nodes in level order

   using array for implementing queue */

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);

        /*Enqueue left child */

        if (temp_node->left)

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

        /*Enqueue right child */

        if (temp_node->right)

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

        /*Dequeue node and make it temp_node*/

        temp_node = deQueue(queue, &front);

    }

}

/*UTILITY FUNCTIONS*/

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];

}

/* Helper function that allocates a new node with the

   given data and NULL left and right pointers. */

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);

}

/* Driver program to test above functions*/

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);

    return 0;

}