Populating Next Right Pointers In Each Node

                                            
# 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 connect(self, root):
        if not root:
            return root
        
        leftmost = root
        while leftmost.left:
            head = leftmost
            while head:
                head.left.next = head.right
                if head.next:
                    head.right.next = head.next.left
                head = head.next
            leftmost = leftmost.left
        
        return root

                                            
/**
 * // Definition for a Node.
 * function Node(val, left, right, next) {
 *    this.val = val === undefined ? null : val;
 *    this.left = left === undefined ? null : left;
 *    this.right = right === undefined ? null : right;
 *    this.next = next === undefined ? null : next;
 * }
 * 
 * @param {Node} root
 * @return {Node}
 */
var connect = function(root) {
    if (!root) return root;
    
    const queue = [root];
    
    while (queue.length > 0) {
        const size = queue.length;
        
        for (let i = 0; i < size; i++) {
            const current = queue.shift();
            
            if (i < size - 1) {
                current.next = queue[0];
            }
            
            if (current.left) queue.push(current.left);
            if (current.right) queue.push(current.right);
        }
    }
    
    return root;
};

                                            
/**
 * Definition for Node.
 * class Node {
 *     val: number;
 *     left: Node | null;
 *     right: Node | null;
 *     next: Node | null;
 *     constructor(val?: number, left?: Node, right?: Node, next?: Node) {
 *         this.val = (val===undefined ? 0 : val);
 *         this.left = (left===undefined ? null : left);
 *         this.right = (right===undefined ? null : right);
 *         this.next = (next===undefined ? null : next);
 *     }
 * }
 */

function connect(root: Node | null): Node | null {
    if (!root) return null;
    
    let levelStart = root;
    
    while (levelStart.left) {
        let curr = levelStart;
        
        while (curr) {
            curr.left.next = curr.right;
            if (curr.next) {
                curr.right.next = curr.next.left;
            }
            
            curr = curr.next;
        }
        
        levelStart = levelStart.left;
    }
    
    return root;
}

                                            
    /**
     * Definition for a Node.
     * class Node {
     *     public $val;
     *     public $left;
     *     public $right;
     *     public $next;
     *     @param Integer $val 
     *     @param Node $left 
     *     @param Node $right 
     *     @param Node $next 
     *     function __construct($val = 0, $left = null, $right = null, $next = null) {
     *         $this->val = $val;
     *         $this->left = $left;
     *         $this->right = $right;
     *         $this->next = $next;
     *     }
     * }
     */
    
    class Solution {
        
        /**
         * @param Node $root
         * @return Node
         */
        function connect($root) {
            if ($root === null) {
                return null;
            }
            
            $this->connectNodes($root->left, $root->right);
            return $root;
        }
        
        function connectNodes($node1, $node2) {
            if ($node1 === null || $node2 === null) {
                return;
            }
            
            $node1->next = $node2;
            
            $this->connectNodes($node1->left, $node1->right);
            $this->connectNodes($node2->left, $node2->right);
            
            $this->connectNodes($node1->right, $node2->left);
        }
    }

                                            
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Left *Node
 *     Right *Node
 *     Next *Node
 * }
 */
 
 func connect(root *Node) *Node {
    if root == nil {
        return root
    }
    
    leftmost := root
    for leftmost.Left != nil {
        head := leftmost
        for head != nil {
            head.Left.Next = head.Right
            if head.Next != nil {
                head.Right.Next = head.Next.Left
            }
            head = head.Next
        }
        leftmost = leftmost.Left
    }
    return root
}

                                            
# Definition for Node.
# class Node
#     attr_accessor :val, :left, :right, :next
#     def initialize(val)
# @param {Node} root
# @return {Node}
def connect(root)
    return nil if root.nil?
    
    queue = [root]
    
    until queue.empty?
        size = queue.size
        prev = nil
        
        size.times do
            node = queue.shift
            prev.next = node if prev
            prev = node
            
            queue << node.left if node.left
            queue << node.right if node.right
        end
    end
    
    root
end

                                            
/**
 * Definition for a Node.
 * class Node(var _value: Int) {
 *   var value: Int = _value
 */
object Solution {
    def connect(root: Node): Node = {
        if (root == null) {
            return null
        }
        if (root.left != null) {
            root.left.next = root.right
            if(root.next != null){
                root.right.next = root.next.left
            }
            connect(root.left)
            connect(root.right)
        }
        root
    }
}

To solve this coding challenge, we need to populate each "next" pointer in a perfect binary tree to point to its next right node. A perfect binary tree is defined as one where all leaf nodes are at the same depth and every parent has exactly two children. Initially, each "next" pointer is set to NULL. The main goal of the algorithm is to traverse the tree level by level, note the connections, and set the next pointers accordingly. Given the constraints, we should aim to use constant space, which generally means avoiding extra data structures like queues or stacks but relying instead on the tree structure itself.

Explanation:

Tree Structure:

The tree provided is a perfect binary tree.
Each node has additional
next

pointers initially set to NULL.

Traversal Technique:

We should use a level-order traversal, also commonly known as a breadth-first traversal, but with constant extra space, this typically means leveraging the connections already present in the tree.

Pointer Manipulations:

Begin from the root node and use a pointer to track the leftmost node of each level.
For each node at a certain level, connect the left child to the right child.
If there is a next node at the same level, connect the right child to the next node's left child.
Move to the next node on the same level using the
next

pointer.
After finishing a level, proceed to the leftmost node of the next level.

Exit Condition:

The traversal stops when reaching the leftmost node of the bottom level, which will not have any children.

Detailed Steps in Pseudocode:

                                            
# Start with a function that connects the nodes

Function connect_nodes(root):
    # If the tree is empty, return the root (which is None)
    If root is NULL:
        return root
        
    # Initialize the current level's leftmost node to the root
    leftmost_node = root
    
    # Iterate while there are more levels (i.e., leftmost_node's left child exists)
    While leftmost_node.left is not NULL:
        
        # Initialize the head of the current level to leftmost_node
        current_node = leftmost_node
        
        # Traverse the current level
        While current_node is not NULL:
            
            # Connect current node's left child to its right child
            current_node.left.next = current_node.right
            
            # If current_node's next is not NULL, connect current node's right child to current node's next's left child
            If current_node.next is not NULL:
                current_node.right.next = current_node.next.left
            
            # Move to the next node at the current level using current_node's next pointer
            current_node = current_node.next
        
        # Move down to the next level
        leftmost_node = leftmost_node.left
    
    # Once all connections are made, return the root
    return root

The function
connect_nodes(root)

begins by checking if the root is NULL and returns if it is.
It uses a while loop to process each level, starting from the root level.
For each node in the current level, the function sets the
next

pointer for its children.
The left child of the current node is connected to the right child of the same node.
If the current node has a next node, the right child is connected to the left child of the next node.
Moving to the leftmost node of the next level by updating the leftmost_node pointer concludes the process.

This process continues until there are no more levels to traverse, ensuring each node's next pointer is correctly populated. Each step leverages the existing structure of the tree to maintain constant space complexity.