Level Order Traversal in a Binary Tree

Level Order Traversal is one of the methods for traversing across a Binary Tree. In this article, we shall look at how we can implement this algorithm in C/C++.

But before that, let us have our concepts covered.

Building the concepts

A Binary Tree is a data structure where every node has at-most two children. The topmost node is called the Root node.

There are 4 common ways of traversing the nodes of a Binary Tree, namely:

• In order Traversal
• Pre Order Traversal
• Post Order Traversal
• Level Order Traversal

Let’s understand what a level in a Binary Tree means.

A level is the number of parent nodes corresponding to a given a node of the tree. It is basically the number of ancestors from that node until the root node.

So, for the root node (topmost node), it’s level is 0, since it has no parents. If it has children, both of them will have a level of 1, since it has only one ancestor until the root node, which is the root node itself.

We also need to understand the notion of height in a Binary Tree. This is simply the length of the path from the root to the deepest node in the tree.

In this case, the height will be the length from the deepest node (40 or 50, since they have the maximum level) to the root. So the height of the tree is 2.

Now that we have our concepts covered, let’s understand how we can implement Level Order Traversal.

Level Order Traversal

A Level Order Traversal is a traversal which always traverses based on the level of the tree.

So, this traversal first traverses the nodes corresponding to Level 0, and then Level 1, and so on, from the root node.

In the example Binary Tree above, the level order traversal will be:

(Root) 10 -> 20 -> 30 -> 40 -> 50

To do this, we need to do 2 things.

1. We must first find the height of the tree
2. We need to find a way to print the nodes corresponding to every level.

Find the height of the Tree

We will find the height of the tree first. To do this, the logic is simple.

Since the height of the tree is defined as the largest path from the root to a leaf. So we can recursively compute the height of the left and right sub-trees, and find the maximum height of the sub-tree. The height of the tree will then simply be the height of the sub-tree + 1.

C- style Pseudo Code:

// Find height of a tree, defined by the root node
int tree_height(Node* root) {
    if (root == NULL) 
        return 0;
    else {
        // Find the height of left, right subtrees
        left_height = tree_height(root->left);
        right_height = tree_height(root->right);
        
        // Find max(subtree_height) + 1 to get the height of the tree
        return max(left_height, right_height) + 1;
}

Print all nodes in every level

Now that we have the height, we must print nodes for every level. To do this, we will use a for loop to iterate all levels until the height, and print nodes at every level.

void print_tree_level_order(Node* root) {
    int height = tree_height(root);
    for (int i=0; i<height; i++) {
        // Print the ith level
        print_level(root, i);
    }
}

Observe that we need another function to print the ith level of the tree.

Here again, we have a similar logic. But this time, after printing the root node, we change the root node to it’s left and right children and print both sub-trees.

This will continue until we reach a leaf node, that is when the auxiliary root will be NULL at the next step. (Since leaf_node->left = NULL and leaf_node->right = NULL)

void print_level(Node* root, int level_no) {
    // Prints the nodes in the tree
    // having a level = level_no
    
    // We have a auxiliary root node
    // for printing the root of every
    // sub-tree
    if (!root)
        return;
    if (level_no == 0) {
        // We are at the top of a sub-tree
        // So print the auxiliary root node
        printf("%d -> ", root->value);
    }
    else {
        // Make the auxiliary root node to
        // be the left and right nodes for
        // the sub-trees and decrease level by 1, since
        // you are moving from top to bottom
        print_level(root->left, level_no - 1);
        print_level(root->right, level_no - 1);
    }

}

Now, we have finally completed the Level Order Traversal!

I will provide the complete program below, which also has a section to construct the Binary Tree using insertion.

Complete C/C++ Code

While this is originally a C program, the same can be compiled on C++ as well.

/**
    Code for https://journaldev.com
    File Name: level_order.c
    Purpose: Find the Level Order Traversal of a Binary Tree

    @author Vijay Ramachandran
    @date 28/01/2020
*/

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

typedef struct Node Node;

// Define the Tree Node here
struct Node {
    int value;
    // Pointers to the left and right children
    Node* left, *right;
};


Node* init_tree(int data) {
    // Creates the tree and returns the
    // root node
    Node* root = (Node*) malloc (sizeof(Node));
    root->left = root->right = NULL;
    root->value = data;
    return root;
}

Node* create_node(int data) {
    // Creates a new node
    Node* node = (Node*) malloc (sizeof(Node));
    node->value = data;
    node->left = node->right = NULL;
    return node;
}

void free_tree(Node* root) {
    // Deallocates memory corresponding
    // to every node in the tree.
    Node* temp = root;
    if (!temp)
        return;
    free_tree(temp->left);
    free_tree(temp->right);
    if (!temp->left && !temp->right) {
        free(temp);
        return;
    }
}

int tree_height(Node* root) {
    // Get the height of the tree
    if (!root)
        return 0;
    else {
        // Find the height of both subtrees
        // and use the larger one
        int left_height = tree_height(root->left);
        int right_height = tree_height(root->right);
        if (left_height >= right_height)
            return left_height + 1;
        else
            return right_height + 1;
    }
}

void print_level(Node* root, int level_no) {
    // Prints the nodes in the tree
    // having a level = level_no
    
    // We have a auxiliary root node
    // for printing the root of every
    // subtree
    if (!root)
        return;
    if (level_no == 0) {
        // We are at the top of a subtree
        // So print the auxiliary root node
        printf("%d -> ", root->value);
    }
    else {
        // Make the auxiliary root node to
        // be the left and right nodes for
        // the subtrees and decrease level by 1, since
        // you are moving from top to bottom
        print_level(root->left, level_no - 1);
        print_level(root->right, level_no - 1);
    }

}

void print_tree_level_order(Node* root) {
    if (!root)
        return;
    int height = tree_height(root);
    for (int i=0; i<height; i++) {
        printf("Level %d: ", i);
        print_level(root, i);
        printf("\n");
    }
    printf("\n\n-----Complete Level Order Traversal:-----\n");
    for (int i=0; i<height; i++) {
        print_level(root, i);
    }
    printf("\n");
}

int main() {
    // Program to demonstrate Level Order Traversal

    // Create the root node having a value of 10
    Node* root = init_tree(10);
    
    // Insert nodes onto the tree
    root->left = create_node(20);
    root->right = create_node(30);
    root->left->left = create_node(40);
    root->left->right = create_node(50);
    
    // Level Order Traversal
    print_tree_level_order(root);

    // Free the tree!
    free_tree(root);
    return 0;
}

Output

Level 0: 10 -> 
Level 1: 20 -> 30 -> 
Level 2: 40 -> 50 -> 


-----Complete Level Order Traversal:-----
10 -> 20 -> 30 -> 40 -> 50 -> 

You can also download this through a Github gist that I created for this purpose. (Contains code for insertion as well)

Conclusion

Hopefully you have a better understanding of how Level Order Traversal can be implemented in C/C++. If you have any questions, feel free to ask them in the comments section below!