Generic Iterative Breadth-First Binary Tree Traversal with Queue in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

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

Breadth-first traversal is also known as level-order traversal. BFS requires the use of a data structure called Queue, which is a First In First Out (FIFO) structure.

                                         Breadth-First Traversal Sequence: 1 - 2 - 3 - 4 - 5 - 6

package interviewquestions;

import java.util.LinkedList;
import java.util.Queue;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void breadthFirst()
   {
     breadthFirst( root );   
   }
 
   private void breadthFirst( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     Queue<Node<T>> queue = new LinkedList<Node<T>>();
     queue.add((Node<T>) pNode);
  
     while (!queue.isEmpty()) {
          Node<T> node = (Node<T>) queue.remove();
          System.out.print(" " + node.getData());
   
          if (node.getLeftChild()!= null)
              queue.add(node.getLeftChild());
          if ( node.getRightChild() != null)
              queue.add(node.getRightChild());
     }      

   }
  
}

public class BreadthFirstTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.breadthFirst();  
 }

}

Create a BreadthFirstTraversal.java file in your workspace.

When the main method inside the BreadthFirstTraversal class executed it is going to print :

1
2
3
4
5
6

Generic Recursive Inorder Binary Tree Traversal in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Inorder traversal allows all the nodes of the binary tree to be visited by applying a recursive algorithm.

This can be summed up as

1. Traverse left subtree
2. Visit root node (output this)
3. Traverse right subtree

Recursive inorder binary tree traversal algorithm can use a generic node class.

                                                 Inorder Traversal Sequence: 4 - 2 - 5 - 1 - 3 - 6

package interviewquestions;

class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void inOrder()
   {
     inOrder( root );   
   }
 
   private void inOrder( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     inOrder( pNode.getLeftChild() );
     System.out.println( pNode.getData() );
     inOrder( pNode.getRightChild() );       

   }
  
}

public class InOrderTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.inOrder();  
 }

}

Create a InOrderTraversal.java file in your workspace.

When the main method inside the InOrderTraversal class executed it is going to print :

4
2
5
1
3
6

Generic Recursive Postorder Binary Tree Traversal in Java

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.

Postorder traversal allows all the nodes of the binary tree to be visited by applying a recursive algorithm.

This can be summed up as

1. Traverse left subtree
2. Traverse right subtree
3. Visit root node (output this)

Recursive postorder binary tree traversal algorithm can use a generic node class.

Postorder Traversal Sequence: 4 - 5 - 2 - 6 - 3 - 1

package interviewquestions;


class Node<T>
{
   private T data;
   private Node<T> left;
   private Node<T> right;
 
   Node( T pData, Node<T> pLeft, Node<T> pRight )
   {
     data = pData;
     left = pLeft;
     right = pRight;
   }
 
   public void setLeftChild( Node<T> pLeft ) {  left = pLeft; }  
   public void setRightChild( Node<T> pRight ) { right = pRight; } 
 
   public Node<T> getLeftChild() { return left; }
   public Node<T> getRightChild() { return right; }  
   public T getData() { return data; }

}

class BinaryTree<T>
{
   Node<T> root;
 
   public BinaryTree(){  root = null; } 
 
   public void setRootNode( Node<T> pRoot ) {  root = pRoot; }
 
   public void postOrder()
   {
     postOrder( root );   
   }
 
   private void postOrder( Node<T> pNode )
   {
     if( pNode == null )
       return;   

     postOrder( pNode.getLeftChild() );
     postOrder( pNode.getRightChild() );

     System.out.println( pNode.getData() );  

   }
  
}

public class PostOrderTraversal {
 
 public static void main(String[] args) {
  
    Node<Integer> node1 = new Node<Integer>( 1, null, null );
    Node<Integer> node2 = new Node<Integer>( 2, null, null );
    Node<Integer> node3 = new Node<Integer>( 3, null, null );
    Node<Integer> node4 = new Node<Integer>( 4, null, null );
    Node<Integer> node5 = new Node<Integer>( 5, null, null );
    Node<Integer> node6 = new Node<Integer>( 6, null, null );
  
    node1.setLeftChild(node2);
    node1.setRightChild(node3);
  
    node2.setLeftChild(node4);
    node2.setRightChild(node5);
  
    node3.setRightChild(node6);
  
    BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
    binaryTree.setRootNode(node1);
  
    binaryTree.postOrder();  
 }

}

Create a PostOrderTraversal.java file in your workspace.

When the main method inside the PostOrderTraversal class executed it is going to print :

4
5
2
6
3
1