import java.util.LinkedList;
import java.util.Queue;
public class App {
static void levelOrderTraversal(TreeNode root){
if(root == null) return;
Queue<TreeNode> myQueue = new LinkedList<>();
myQueue.add(root);
// sebagai penanda tanda ganti level
myQueue.add(null);
// selama queue tidak kosong, pop queue
while(!myQueue.isEmpty()){
TreeNode current = myQueue.poll();
// jika elemen null padahal tree tidak kosong, artinya level berakhir
if(current==null){
if(!myQueue.isEmpty()){
// sebagai penanda tanda ganti level
myQueue.add(null);
}
}else {
// push anak kiri dahulu sebelum anak kanan
if (current.leftChild != null)
myQueue.add(current.leftChild);
if (current.rightChild != null)
myQueue.add(current.rightChild);
System.out.print(current.data + " ");
}
}
}
public static void main(String[] args) throws Exception {
TreeNode root = new TreeNode(1);
root.leftChild = new TreeNode(2);
root.rightChild = new TreeNode(3);
root.leftChild.leftChild = new TreeNode(4);
root.leftChild.rightChild = new TreeNode(5);
root.rightChild.leftChild = new TreeNode(6);
root.rightChild.rightChild = new TreeNode(7);
root.leftChild.leftChild.leftChild = new TreeNode(8);
root.leftChild.leftChild.rightChild = new TreeNode(9);
root.leftChild.rightChild.leftChild = new TreeNode(10);
root.leftChild.rightChild.rightChild = new TreeNode(11);
levelOrderTraversal(root);
}
}
class TreeNode{
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode(int data){
this.data=data;
leftChild = null;
rightChild = null;
}
}