Level Order Traversal

Level Order Traversal visits all nodes present in the same level completely before visiting the next level.

Algorithm for Level Order Traversal:

LevelOrder(tree)

Create an empty queue Q
Enqueue the root node of the tree to Q
Loop while Q is not empty
Dequeue a node from Q and visit it
Enqueue the left child of the dequeued node if it exists
Enqueue the right child of the dequeued node if it exists

Uses of Level Order:

Level Order Traversal is mainly used as Breadth First Search to search or process nodes level-by-level.
Level Order traversal is also used for Tree Serialization and Deserialization.

Code Snippet for Level Order Traversal:

C++

// Iterative method to find height of Binary Tree
void printLevelOrder(Node* root)
{
    // Base Case
    if (root == NULL)
        return;

    // Create an empty queue for level order traversal
    queue<Node*> q;

    // Enqueue Root and initialize height
    q.push(root);

    while (q.empty() == false) {

        // Print front of queue and remove it from queue
        Node* node = q.front();
        cout << node->data << " ";
        q.pop();

        // Enqueue left child
        if (node->left != NULL)
            q.push(node->left);

        // Enqueue right child
        if (node->right != NULL)
            q.push(node->right);
    }
}

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

Java

// Given a binary tree. Print
// its nodes in level order
// using array for implementing queue
void printLevelOrder()
{
    Queue<Node> queue = new LinkedList<Node>();
    queue.add(root);
    while (!queue.isEmpty()) {

        // poll() removes the present head.
        Node tempNode = queue.poll();
        System.out.print(tempNode.data + " ");

        // Enqueue left child
        if (tempNode.left != null) {
            queue.add(tempNode.left);
        }

        // Enqueue right child
        if (tempNode.right != null) {
            queue.add(tempNode.right);
        }
    }
}

Python3

# Iterative Method to print the
# height of a binary tree


def printLevelOrder(root):

    # Base Case
    if root is None:
        return

    # Create an empty queue
    # for level order traversal
    queue = []

    # Enqueue Root and initialize height
    queue.append(root)

    while(len(queue) > 0):

        # Print front of queue and
        # remove it from queue
        print(queue[0].data, end=" ")
        node = queue.pop(0)

        # Enqueue left child
        if node.left is not None:
            queue.append(node.left)

        # Enqueue right child
        if node.right is not None:
            queue.append(node.right)

// Given a binary tree. Print
// its nodes in level order using
// array for implementing queue
void printLevelOrder()
{
    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(root);
    while (queue.Count != 0) {

        Node tempNode = queue.Dequeue();
        Console.Write(tempNode.data + " ");

        // Enqueue left child
        if (tempNode.left != null) {
            queue.Enqueue(tempNode.left);
        }

        // Enqueue right child
        if (tempNode.right != null) {
            queue.Enqueue(tempNode.right);
        }
    }
}

JavaScript

// Function to perform level order traversal of a binary tree
function printLevelOrder(root) {
    // Create a deque to store nodes for traversal
    const queue = new Deque();
    // Add the root node to the queue
    queue.enqueue(root);
    // Continue traversal until the queue is empty
    while (!queue.isEmpty()) {
        // Remove and get the first node from the queue
        const tempNode = queue.dequeue();
        // Print the data of the current node
        console.log(tempNode.data + " ");

        // Enqueue the left child if it exists
        if (tempNode.left !== null) {
            queue.enqueue(tempNode.left);
        }
        // Enqueue the right child if it exists
        if (tempNode.right !== null) {
            queue.enqueue(tempNode.right);
        }
    }
}

Tree Traversal Techniques – Data Structure and Algorithm Tutorials

Tree Traversal techniques include various ways to visit all the nodes of the tree. Unlike linear data structures (Array, Linked List, Queues, Stacks, etc) which have only one logical way to traverse them, trees can be traversed in different ways. In this article, we will discuss about all the tree traversal techniques along with their uses.

Table of Content

Tree Traversal Meaning
Tree Traversal Techniques
Inorder Traversal
Preorder Traversal
Postorder Traversal
Level Order Traversal
Other Tree Traversals
Frequently Asked Questions (FAQs) on Tree Traversal Techniques

Level Order Traversal

Tree Traversal Techniques – Data Structure and Algorithm Tutorials

Similar Reads

Contact Us