import java.util.*;

/*class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;
  TreeNode next;

  TreeNode(int x) {
    val = x;
    left = right = next = null;
  }
};*/

class Solution {
  public TreeNode connect(TreeNode root) {
    if (root == null) {
      return root;
    }
    solve(root);
    return root;
  }

  public void solve(TreeNode root) {

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);

    while(!queue.isEmpty()) {

      int levelSize = queue.size();

      for (int i = 0; i<levelSize; i++) {

        TreeNode node = queue.poll();

        if (i == levelSize-1) {
          node.next = null;
        } else {
	        node.next = queue.peek();
        }

        if (node.left != null) {
          queue.offer(node.left);
        }

        if (node.right != null) {
          queue.offer(node.right);
        }
      }
    }
  }
}