Program: Implement Binary Search Tree (BST) Level order traversal (breadth first).

For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right subtree of the root node should be greater than the data of the root. This example shows the implementation of a binary search tree level order traversal (breadth first).

What is Level order traversal (breadth first)?

In Level order traversal, we visit every node on a level before going to a lower level from left to right. This is also known as Breadth first traversal as the search tree is broadened as much as possible on each depth before going to the next depth. Below picture shows the level order traversal.

Here is an example picture of binary search tree (BST) for our example code:

Here is the steps to implement Level order traversal:

1. Since we have to traverse in same level until we cover all nodes in the same level, it is hard to keep the node references, we will maintain a queue for storing all discovered nodes.
2. Initially the queue will be empty.
3. If the root node is not null, push it to the queue.
4. Use a while loop to visit all nodes in the queue until the queue is empty.
5. Inside while loop, pop out the node.
6. Add the left node to the queue if it is not null.
7. Add the right node to the queue if it is not null.
8. Read the node data and display it.
9. Repeat from step 5, until the queue is empty.

package com.java2novice.ds;

public class BstNode {

	private BstNode left;
	private BstNode right;
	private Integer data;

	public BstNode(Integer data) {
		this.data = data;
	}

	public BstNode getLeft() {
		return left;
	}
	public void setLeft(BstNode left) {
		this.left = left;
	}
	public BstNode getRight() {
		return right;
	}
	public void setRight(BstNode right) {
		this.right = right;
	}

	public Integer getData() {
		return data;
	}
}

package com.java2novice.ds;

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

public class BinarySearchTreeImpl {

	private BstNode root;

	public boolean isEmpty() {

		return (this.root == null);
	}

	public void insert(Integer data) {

		System.out.print("[input: "+data+"]");
		if(root == null) {
			this.root = new BstNode(data);
			System.out.println(" -> inserted: "+data);
			return;
		}

		insertNode(this.root, data);
		System.out.print(" -> inserted: "+data);
		System.out.println();
	}

	private BstNode insertNode(BstNode root, Integer data) {

		BstNode tmpNode = null;
		System.out.print(" ->"+root.getData());
		if(root.getData() >= data) {
			System.out.print(" [L]");
			if(root.getLeft() == null) {
				root.setLeft(new BstNode(data));
				return root.getLeft();
			} else {
				tmpNode = root.getLeft();
			}
		} else {
			System.out.print(" [R]");
			if(root.getRight() == null) {
				root.setRight(new BstNode(data));
				return root.getRight();
			} else {
				tmpNode = root.getRight();
			}
		}

		return insertNode(tmpNode, data);
	}

	public void levelOrderTraversal() {

		Queue<BstNode> discovedNodeQueue = new LinkedList<>();
		if(this.root == null) {
			System.out.println("The tree is empty.");
			return;
		}
		discovedNodeQueue.add(this.root);
		while (!discovedNodeQueue.isEmpty()) {

			BstNode tmpNode = discovedNodeQueue.remove();
			if(tmpNode.getLeft() != null) { discovedNodeQueue.add(tmpNode.getLeft()); }
			if(tmpNode.getRight() != null) { discovedNodeQueue.add(tmpNode.getRight()); }
			System.out.print(tmpNode.getData()+" ");
		}
	}

	public static void main(String a[]) {

		BinarySearchTreeImpl bst = new BinarySearchTreeImpl();
		bst.insert(8);
		bst.insert(10);
		bst.insert(14);
		bst.insert(3);
		bst.insert(6);
		bst.insert(7);
		bst.insert(1);
		bst.insert(4);
		bst.insert(13);
		System.out.println("-------------------");
		System.out.println("Level order traversal");
		bst.levelOrderTraversal();
	}
}

[input: 8] -> inserted: 8
[input: 10] ->8 [R] -> inserted: 10
[input: 14] ->8 [R] ->10 [R] -> inserted: 14
[input: 3] ->8 [L] -> inserted: 3
[input: 6] ->8 [L] ->3 [R] -> inserted: 6
[input: 7] ->8 [L] ->3 [R] ->6 [R] -> inserted: 7
[input: 1] ->8 [L] ->3 [L] -> inserted: 1
[input: 4] ->8 [L] ->3 [R] ->6 [L] -> inserted: 4
[input: 13] ->8 [R] ->10 [R] ->14 [L] -> inserted: 13
-------------------
Level order traversal
8 3 10 1 6 14 4 7 13