Given a binary tree

struct Node { int val; Node *left; Node *right; Node *next; }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to `NULL`

.

Initially, all next pointers are set to `NULL`

.

**Example:**

Input:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":null,"next":null,"right":{"$id":"6","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}Output:{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":null,"right":null,"val":7},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"6","left":null,"next":null,"right":{"$ref":"5"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"6"},"val":1}Explanation:Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

### Note:

- You may only use constant extra space.
- Recursive approach is fine, implicit stack space does not count as extra space for this problem.

## Approach

The idea is to do level order traversal, but instead of using queue, we shall use node’s next node pointer.

- Step1: From the current root element,
**connect next level’s nodes**, with help of**2 pointers**(*childHead*and*child*).**childHead**points to next level’s head node and**child**pointer is next level’s traversal pointer. - Step2:
**Move to next item on the current level**using next pointer. Once we reach END of current level, point current root to next level’s head using**childHead**and continue the same process.

public Node Connect(Node root) { Node rootPointer = root; //maintain 2 pointers Node childHead = null; //NEXT level's head pointer Node child = null; //NEXT level's traversal pointer while (root !=null ) { //******************************************* //Step1: build child level's next pointers //******************************************* //if current item has left child if (root.left !=null ) { //mark child level's head if it is not done if(childHead ==null) { //both child and childHead point to left node childHead = root.left; child = root.left; } else { //attach child next to root's left node child.next = root.left; //move to child's next child = child.next; } } if (root.right !=null) { //mark child level's head if it is not done if(childHead ==null) { //both child and childHead point to right node childHead = root.right; child = root.right; } else { //attach child next to root's right node child.next = root.right; //move to child's next child = child.next; } } //******************************************* //Step2: move to next item on SAME level //******************************************* root = root.next; //******************************************* //Step3: Once we reach END of current level //******************************************* if(root ==null) { //go to next LEVEL root = childHead; //reset child and childHead pointers childHead = null; child = null; } } return rootPointer; }