Level Order traversal of a Binary Tree

Simple level order traversal:

private void levelOrder(Node node) {
if (null == node) { return ; }
Queue<Node> queue = new LinkedList<Node>();
queue.add(node);

while (!queue.isEmpty()) {
Node tempNode = queue.remove();
System.out.print(tempNode.data + " -> ");

if (tempNode.left != null) {
queue.add(tempNode.left);
}
if (tempNode.right != null) {
queue.add(tempNode.right);
}
}
System.out.println("null");
}

Level Order Binary Tree traversal using marker node:


private void printLevelOrderBT(Node root) {
if (null == root) { return ; }
Queue<Node> queue = new LinkedList<Node>();
Node marker = new Node(Integer.MIN_VALUE);
queue.add(root);
queue.add(marker);

while (!queue.isEmpty()) {
Node node = queue.remove();

if (node.equals(marker)) {
System.out.println();

if (!queue.isEmpty()) {
queue.add(marker);
}

} else {
System.out.print(node.data + " ");
}

if (node.left != null) {
queue.add(node.left);
}

if (node.right != null) {
queue.add(node.right);
}
}

}

Level Order Binary Tree traversal using Two Queues:


private void levelOrderTwoQ(Node root) {
if (null == root) { return ;}

Queue<Node> firstQ = new LinkedList<Node>();
Queue<Node> secondQ = new LinkedList<Node>();

firstQ.add(root);

while (!firstQ.isEmpty() || !secondQ.isEmpty()) {
while (!firstQ.isEmpty()) {
Node node = firstQ.remove();
System.out.print(node.data + " ");
if (node.left != null) {
secondQ.add(node.left);
}
if (node.right != null) {
secondQ.add(node.right);
}
}
System.out.println();

while (!secondQ.isEmpty()) {
Node node = secondQ.remove();
System.out.print(node.data + " ");
if (node.left != null) {
firstQ.add(node.left);
}
if (node.right != null) {
firstQ.add(node.right);
}
}
System.out.println();
}
}