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.

&nbsp;
Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
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. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.


Example 2:

Input: root = []
Output: []


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [0, 6000].
	-100 &lt;= Node.val &lt;= 100


&nbsp;
Follow-up:


	You may only use constant extra space.
	The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.


"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution(object):
    def findRightMost(self, root, level, requiredLevel):
        if not root:
            return root
        if level == requiredLevel:
            return root
        right = self.findRightMost(root.right, level + 1, requiredLevel)
        if right:
            return right
        return self.findRightMost(root.left, level + 1, requiredLevel)
    def findLeftMost(self, root, level, requiredLevel):
        if not root:
            return root
        if level == requiredLevel:
            return root
        left = self.findLeftMost(root.left, level + 1, requiredLevel)
        if left:
            return left
        return self.findLeftMost(root.right, level + 1, requiredLevel)
    def findRightMostFromRoot(self, rootLevelInfo, requiredLevel, currentRight):
        if currentRight:
            if currentRight.right:
                return currentRight.right
            if currentRight.left:
                return currentRight.left
        root, rootlevel = rootLevelInfo
        rightMost = self.findRightMost(root, rootlevel, requiredLevel)
        while not rightMost and root:
            root = root.right if root.right else root.left
            rootlevel += 1
            rightMost = self.findRightMost(root, rootlevel, requiredLevel)
            if rightMost:
                rootLevelInfo[-1] = rootlevel
                rootLevelInfo[0] = root
        return rightMost
    def findLeftMostFromRoot(self, rootLevelInfo, requiredLevel, currentLeft):
        if currentLeft:
            if currentLeft.left:
                return currentLeft.left
            if currentLeft.right:
                return currentLeft.right
        root, rootlevel = rootLevelInfo
        leftMost = self.findLeftMost(root, rootlevel, requiredLevel)
        while not leftMost and root:
            root = root.left if root.left else root.right
            rootlevel += 1
            leftMost = self.findLeftMost(root, rootlevel, requiredLevel)
            if leftMost:
                rootLevelInfo[-1] = rootlevel
                rootLevelInfo[0] = root

        return leftMost
    def stitch(self, root):
        if not root:
            return
        leftRootStart = [root.left, 1]
        rightRootStart = [root.right, 1]
        connectLevel = 1
        currentLeft = self.findLeftMostFromRoot(rightRootStart, 1, None)
        currentRight = self.findRightMostFromRoot(leftRootStart, 1, None)
        while currentLeft and currentRight:
            currentRight.next = currentLeft
            connectLevel += 1
            currentLeft = self.findLeftMostFromRoot(rightRootStart, connectLevel, currentLeft)
            currentRight = self.findRightMostFromRoot(leftRootStart, connectLevel, currentRight)

        self.stitch(root.left)
        self.stitch(root.right)
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        if not root:
            return root
        self.stitch(root)
        return root
class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Node head = null; //the start node of next level, the first left of next level
        Node prev = null; //the next pointer
        Node curr = root;

        while (curr != null) {
            //traverse the whole current level, left -> right, until we meet a null pointer
            while (curr != null) {
                if (curr.left != null) {
                    if (head == null) {
                        head = curr.left;
                        prev = curr.left;
                    } else {
                        prev.next = curr.left;
                        prev = prev.next;
                    }
                }

                if (curr.right != null) {
                    if (head == null) {
                        head = curr.right;
                        prev = curr.right;
                    } else {
                        prev.next = curr.right;
                        prev = prev.next;
                    }
                }
                curr = curr.next;
            }

            curr = head;
            prev = null;
            head = null;
        }
        return root;
    }
}
// method-1
class Solution {
public:
    Node* connect(Node* root) {
        if(!root)
            return NULL;
        queue<Node*> q;
        q.push(root);
        root->next=NULL;

        while(!q.empty()){

            int size=q.size();
            Node* prev=NULL;

            for(int i=0;i<size;i++){
                Node* temp=q.front();
                q.pop();

                if(prev)
                    prev->next=temp;

                if(i==size-1){
                    temp->next=NULL;
                }

                if(temp->left)
                    q.push(temp->left);

                if(temp->right)
                    q.push(temp->right);

                prev=temp;

            }
        }

        return root;
    }
};
var connect = function(root) {
    let curr = root;
    
    while (curr != null) {
        let start = null; // (1)
        let prev = null;
    
        while (curr != null) { // (2)
            if (start == null) { // (3)
                if (curr.left) start = curr.left;
                else if (curr.right) start = curr.right;
                
                prev = start; // (4)
            }
            
            if (prev != null) {
                if (curr.left && prev != curr.left) {
                    prev = prev.next = curr.left; // (5)
                }
                if (curr.right && prev != curr.right) {
                    prev = prev.next = curr.right;
                }
            }

            curr = curr.next; // (6)
        }
		
        curr = start; // (7)
    }
    
    return root;
};
Populating Next Right Pointers in Each Node II