import java.util.* ;
import java.io.*;
/*
Following is the structure used to represent the Binary Tree Node
class BinaryTreeNode<T> {
T val;
BinaryTreeNode<T> left;
BinaryTreeNode<T> right;
public BinaryTreeNode(T val) {
this.val = val;
this.left = null;
this.right = null;
}
}
*/
import java.util.ArrayList;
public class Solution
{
public static ArrayList<Integer> getLevelOrder(BinaryTreeNode root)
{
// tree is empty
if(root==null)
{
return new ArrayList<>();
}
//create the arraylist to sore ans
ArrayList<Integer> ans = new ArrayList<>();
//create the queue (use proprty of queue which is fifo )
Queue<BinaryTreeNode> q1=new LinkedList<>();
//add fist root node and null manually in queu
q1.add(root);
q1.add(null);
//traverse the queu
while(!q1.isEmpty())
{
BinaryTreeNode currentNode = q1.remove();
// current node is empty
if(currentNode==null)
{
System.out.println();
//if queu is empty check beause adding null everytime
if(q1.isEmpty())
{
break;
}
else
{
q1.add(null);
}
}
else
{
ans.add(currentNode.val);
if(currentNode.left!=null)
{
q1.add(currentNode.left);
}
if(currentNode.right!=null)
{
q1.add(currentNode.right);
}
}
}
return ans;
}
}