Binary Tree Level Order Traversal in Java

ghz 10months ago ⋅ 94 views

1. Introduction

Binary Tree Level Order Traversal is a technique used to traverse all nodes of a binary tree level by level, starting from the root node and moving downwards. This traversal technique is also known as breadth-first traversal.

2. What is Level Order Traversal?

Level Order Traversal visits nodes level by level, starting from the root node at level 0, then visiting all nodes at level 1, followed by nodes at level 2, and so on. Within each level, nodes are visited from left to right.

3. Process of Level Order Traversal

The process of Level Order Traversal typically involves using a queue data structure to keep track of the nodes at each level. The algorithm follows these steps:

  1. Enqueue the root node into the queue.
  2. Repeat the following steps until the queue is empty:
    • Dequeue a node from the queue.
    • Process the dequeued node.
    • Enqueue its left child (if exists).
    • Enqueue its right child (if exists).
  3. Continue until all nodes have been processed.

4. Complete Java Program

Here's a Java program to perform Level Order Traversal of a binary tree:

import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class LevelOrderTraversal {
    public static void main(String[] args) {
        // Example binary tree
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("Level Order Traversal:");
        levelOrderTraversal(root);
    }

    public static void levelOrderTraversal(TreeNode root) {
        if (root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            System.out.print(node.val + " ");

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
    }
}

5. Complexity of Algorithm

The time complexity of the Level Order Traversal algorithm is O(n), where n is the number of nodes in the binary tree. This is because each node is visited exactly once.

6. Conclusion

Binary Tree Level Order Traversal is a fundamental technique for visiting all nodes in a binary tree level by level. It can be implemented efficiently using a queue data structure. This traversal technique is widely used in various tree-related algorithms and applications.

#algorithm