Breadth First Search tree in Java

Breadth-first search (BFS) is an algorithm for traversing or searching a graph, tree, or other data structure. It starts at the root node and explores the neighbor nodes first, before moving to the next level neighbors.

Here is an example of how you might implement breadth-first search in Java:

import java.util.ArrayDeque;

import java.util.Deque;

class Node {

  int data;

  Node left;

  Node right;

  public Node(int data, Node left, Node right) {

    this.data = data;

    this.left = left;

    this.right = right;

  }

}

class BinaryTree {

  private Node root;

  public BinaryTree(Node root) {

    this.root = root;

  }

  public void breadthFirstSearch() {

    Deque<Node> queue = new ArrayDeque<>();

    queue.add(root);

    while (!queue.isEmpty()) {

      Node node = queue.pollFirst();

      System.out.println(node.data);

      if (node.left != null) {

        queue.add(node.left);

      }

      if (node.right != null) {

        queue.add(node.right);

      }

    }

  }

}

You can then use the breadthFirstSearch method to perform a breadth-first search on a binary tree as follows:

// Create a binary tree

Node leaf1 = new Node(1, null, null);

Node leaf2 = new Node(2, null, null);

Node node1 = new Node(3, leaf1, leaf2);

Node leaf3 = new Node(4, null, null);

Node root = new Node(5, node1, leaf3);

BinaryTree tree = new BinaryTree(root);

// Perform a breadth-first search on the tree

tree.breadthFirstSearch();

// Outputs 5, 3, 4, 1, 2