HelloKoding

Practical coding guides

Breadth First Traversal in Tree

In this article, you will learn about the breadth-first traversal operation in a Tree data structure

Tree traversal is a process of visiting each node in a tree exactly once. Unlike linear data structures such as array and linked list which is canonically traversed in linear order, a tree may be traversed in depth-first or breadth-first order

Breadth-First Traversal

Visit all nodes on the current level before going to lower levels

a Binary Search Tree

For the above tree, assuming that the left subtree are chosen before the right subtree, breadth-first traversal orders will be 7-2-9-1-3

Implementation with Iterative algorithm

TreeBreadthFirstTraversal.java

package com.hellokoding.algorithm;

import com.hellokoding.datastructure.BSTByLinkedList;

import java.util.ArrayDeque;
import java.util.Queue;

public class TreeBreadthFirstTraversal extends BSTByLinkedList {
    void breadthFirstTraversal(Node root) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            Node currentNode = queue.poll();
            System.out.println(currentNode);

            if (currentNode.left != null)
                queue.offer(currentNode.left);

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

    public static void main(String[] args) {
        TreeBreadthFirstTraversal tree = new TreeBreadthFirstTraversal();
        tree.insert(7);
        tree.insert(2);
        tree.insert(3);
        tree.insert(1);
        tree.insert(9);

        tree.breadthFirstTraversal(tree.root);
    }
}

BSTByLinkedList is defined in Binary Search Tree Data Structure

Follow HelloKoding