Traversing a Binary Tree in Level-Order

Traversing a binary tree in level-order means visiting all the nodes in the tree level by level, starting from the root and moving down to the leaves.

In this post, we will take a look at the implementation in C using a queue data structure.

Data Structures

struct binary_tree_s
{
    int n;
    struct binary_tree_s *left;
    struct binary_tree_s *right;
};

typedef struct binary_tree_s binary_tree_t;

Implementation

• First, we check that the input binary tree is not empty.

/* if tree is NULL */
if (tree == NULL)
{
    return;
}

• Next, we create a queue data structure to store the nodes of the binary tree that need to be added.

/* create queue to store node items */
binary_tree_t **queue = malloc(sizeof(*queue) * 1024);
if (queue == NULL) /* malloc fails */
{
    return;
}

• We add the root node of the tree to the queue, the queue's tail and size are then incremented.

int head, tail, size, i;
head = tail = size = 0; /* initialize to zero */
queue[0] = tree; /* add root node to queue */
tail = size = 1; /* tail and size increases by 1 */

• Our function then enters a loop that iterates over the items in the queue.
• For each item in the queue, the function prints the value of the node's data.
• If the current node has a left child, the left child is added to the queue, and the queue's tail is incremented.
• If the current node has a right child, the right child is added to the queue, and the queue's tail is incremented.
• Once all the nodes in the current level have been added to the queue, the head and size indices are updated to prepare for adding the next level. This continues until all nodes in the tree have been added.

while (head < size) /* iterate over the items in the queue */
{
    for (i = head; i < size; i++)
    {
        printf("%d\n", queue[i]->n); /* print value */

        if (queue[i]->left) /* check if a left child exists */
        {
            queue[tail] = queue[i]->left; /* last item in queue now points to left */
            tail++; /* tail increases */
        }

        if (queue[i]->right) /* check if a right child exists */
        {
            queue[tail] = queue[i]->right; /* last item in queue now points to right */
            tail++; /* tail increases */
        }
    }

    /* head becomes size this indicates the number of items that have been iterated/printed */
    head = size;
    /* size becomes tail, this is the number of items in the queue */
    size = tail;
}

• Finally, we free the memory allocated for the queue.

free(queue); /* free queue */

Output

Tree is printed using level-order traversal.

binary_trees$ ./level_order
       .-------(098)-------.
  .--(012)--.         .--(402)--.
(006)     (056)     (256)     (512)
98
12
402
6
56
256
512
binary_trees$