package com.sunny.grokkingalgorithms.gfg.mustdo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by sundas on 11/22/2017.
 */
class Node
{
  int data;
  Node left, right, nextRight;
  Node(int item)
  {
    data = item;
    left = right = nextRight = null;

  }
}
public class ConnectNodesAtSameLevel {

  //https://practice.geeksforgeeks.org/problems/connect-nodes-at-same-level/1


  /**
   *
   * @param root
   */
  public static void connect(Node root){
    /*
    We could essentially use bfs and stitch nodes at each level using a previous pointer
     */
    if(root != null) {
      Queue<Node> bfsQueue = new LinkedList<>();
      bfsQueue.add(root);
      Node levelMarker = new Node(-1);
      bfsQueue.add(levelMarker);
      Node previousNodeInThisLevel = null;
      while(!bfsQueue.isEmpty()){
        Node current = bfsQueue.poll();
        if(current == levelMarker){
          previousNodeInThisLevel = null;
          if(!bfsQueue.isEmpty()) {
            bfsQueue.add(levelMarker);
          }
        }
        else{
          if(current != null){
            if(current.left != null){
              bfsQueue.add(current.left);
            }
            if(current.right != null){
              bfsQueue.add(current.right);
            }
          }
          if(previousNodeInThisLevel != null){
            previousNodeInThisLevel.nextRight = current;
          }
          previousNodeInThisLevel = current;
        }
      }
    }
  }

  /**
   *
   * @param args
   */
  public static void main(String[] args) {

  }

}

@@ -1477,16 +1477,1836 @@
  %7D%0A  %7D%0A%0A
+  /**%0A   * The Editorial solution using O(1) space%0A   *%0A   */%0A  public static void connectEditorial(Node root)%7B%0A    /**%0A     * Base case%0A     */%0A    if(root == null)%7B%0A      return;%0A    %7D%0A    if(root.left == null && root.right == null)%7B%0A      return;%0A    %7D%0A    /**%0A     * normal use case%0A     * At level one we will get connected nodes and then we build on it each node%0A     */%0A    if(root.left != null && root.right != null)%7B%0A      root.left.nextRight = root.right;%0A      Node temp = root.nextRight;%0A      while(temp != null%0A          && temp.left == null%0A          && temp.right == null)%7B%0A        temp = temp.nextRight;%0A      %7D%0A      if(temp == null)%7B%0A        root.right.nextRight = null;%0A      %7D%0A      else if(temp.left != null)%7B%0A        root.right.nextRight = temp.left;%0A      %7D%0A      else if(temp.right != null)%7B%0A        root.right.nextRight = temp.right;%0A      %7D%0A    %7D%0A    if(root.right == null)%7B%0A      Node temp = root.nextRight;%0A      while(temp != null%0A          && temp.left == null%0A          && temp.right == null)%7B%0A        temp = temp.nextRight;%0A      %7D%0A      if(temp == null)%7B%0A        root.left.nextRight = null;%0A      %7D%0A      else if(temp.left != null)%7B%0A        root.left.nextRight = temp.left;%0A      %7D%0A      else if(temp.right != null)%7B%0A        root.left.nextRight = temp.right;%0A      %7D%0A    %7D%0A    else if(root.left == null)%7B%0A      Node temp = root.nextRight;%0A      while(temp != null%0A          && temp.left == null%0A          && temp.right == null)%7B%0A        temp = temp.nextRight;%0A      %7D%0A      if(temp == null)%7B%0A        root.right.nextRight = null;%0A      %7D%0A      else if(temp.left != null)%7B%0A        root.right.nextRight = temp.left;%0A      %7D%0A      else if(temp.right != null)%7B%0A        root.right.nextRight = temp.right;%0A      %7D%0A    %7D%0A    connectEditorial(root.left);%0A    connectEditorial(root.right);%0A  %7D%0A%0A%0A
   /**%0A  

Connect nodes at same level with binary tree using recursion , alternative to bfs solution , refer here for understanding : http://javabypatel.blogspot.in/2015/08/connect-nodes-at-same-level-in-binary-tree-using-constant-extra-space.html