content: package trees;
  
  import java.util.ArrayDeque;
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Queue;
  
  public class LevelOrderTraversal {
  
  
      /*
       * Given root of a binary tree, display node values at each level. Node values for all levels should be displayed on separate lines.
       *
       *  Binary Node: 100, 50, 200, 25, 75, 125, 350
       *  Level order traversal for this tree should look like:
       *  100
       *  50, 200
       *  25, 75, 350
       *
       *  Runtime Complexity:
       *  Linear, O(n)
       *
       *  Memory Complexity:
       *  Linear, O(n)
       *
       *
       * */
  
      private static class Node {
          private int data;
          private Node left, right;
  
          Node(int item) {
              data = item;
              left = right = null;
          }
  
          public int getData() {
              return data;
          }
  
          public Node getLeft() {
              return left;
          }
  
          public Node getRight() {
              return right;
          }
      }
  
  
      private Node root1;
  
      protected static void levelOrderTraversal(Node root) {
  
          if (root == null) {
              return;
          }
  
          List<Queue<Node>> queues = new ArrayList<>();
          queues.add(new ArrayDeque<>());
          queues.add(new ArrayDeque<>());
  
          Queue<Node> currentQueue = queues.get(0);
          Queue<Node> nextQueue = queues.get(1);
  
          currentQueue.add(root);
          int levelNumber = 0;
  
          while (!currentQueue.isEmpty()) {
              Node temp = currentQueue.poll();
              System.out.print(temp.data + ",");
  
              if (temp.left != null) {
                  nextQueue.add(temp.left);
              }
  
              if (temp.right != null) {
                  nextQueue.add(temp.right);
              }
  
              if (currentQueue.isEmpty()) {
                  System.out.println();
                  ++levelNumber;
                  currentQueue = queues.get(levelNumber % 2);
                  nextQueue = queues.get((levelNumber + 1) % 2);
              }
          }
          System.out.println();
      }
  
  
  
      public static void main(String[] argv) {
          
          LevelOrderTraversal levelOrderTraversal = new LevelOrderTraversal();
          levelOrderTraversal.root1 = new Node(100);
          levelOrderTraversal.root1.left = new Node(50);
          levelOrderTraversal.root1.right = new Node(200);
          levelOrderTraversal.root1.left.left = new Node(25);
          levelOrderTraversal.root1.left.right = new Node(75);
          levelOrderTraversal.root1.right.left = new Node(125);
          levelOrderTraversal.root1.right.right = new Node(350);
          
          levelOrderTraversal(levelOrderTraversal.root1);
          System.out.println();
      }
  }
  