content: package trees;
  
  import java.util.ArrayDeque;
  import java.util.ArrayList;
  import java.util.List;
  import java.util.Queue;
  
  public class ConnectAllSiblings {
  
  
      /*
       * Given the root to a binary tree where each node has an additional pointer called sibling (or next),
       * connect the sibling pointer to next node in the same level. Last node in each level should point
       * to the first node of next level in the tree.
       *
       * Runtime Complexity:
       * Linear, O(n)
       *
       * Memory Complexity:
       * Constant O(1)
       *
       * Step 1: Initially set both current and last as 'root'
       * Step 2: while current node is not null
       *      If current node has a left child, append this left node to the last and make it last node.
       *      If current node has a right child, append this right node to the last and make it last node.
       *      update current node to current's next node
       * */
  
      protected static class Node {
          int data;
          Node left, right, next;
  
          Node(int item) {
              data = item;
              left = right = next = null;
          }
      }
  
  
      private Node root;
  
      public static void populateSiblingPointers(Node root) {
          if (root == null)
              return;
  
          Node current = root;
          Node last = root;
  
          while (current != null) {
              if (current.left != null) {
                  last.next = current.left;
                  last = current.left;
              }
  
              if (current.right != null) {
                  last.next = current.right;
                  last = current.right;
              }
  
              last.next = null;
              current = current.next;
          }
      }
  
  
      protected 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[] args) {
  
          ConnectAllSiblings tree = new ConnectAllSiblings();
          tree.root = new Node(100);
          tree.root.left = new Node(50);
          tree.root.right = new Node(200);
          tree.root.left.left = new Node(25);
          tree.root.left.right = new Node(75);
          tree.root.right.right = new Node(300);
          tree.root.right.right.right = new Node(350);
  
          Node root = tree.root;
  
          tree.levelOrderTraversal(root);
          populateSiblingPointers(root);
  
          System.out.println("Root -> next: " + root.next.data); //25
  //        System.out.println("Root->right->left->next: " + root.right.left.next.data); //400
          System.out.println("Root->right->right->next: " + root.right.right.next.data); //10
  //        System.out.println("Root->right->right->left->next: " + root.right.right.left.next); //None
      }
  
  }
  