Code Implementation

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

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        if not root:
            return None
        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.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (!root) return nullptr;
        Node* leftmost = root;
        while (leftmost->left) {
            Node* 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.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    public Node(int val) { this.val = val; }
    public Node(int val, Node left, Node right, Node next) {
        this.val = val;
        this.left = left;
        this.right = right;
        this.next = next;
    }
}
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) return null;
        Node leftmost = root;
        while (leftmost.left != null) {
            Node head = leftmost;
            while (head != null) {
                head.left.next = head.right;
                if (head.next != null)
                    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 ? 0 : 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 null;
    let leftmost = root;
    while (leftmost.left) {
        let 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;
};
      

Problem Description

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. Each node in this tree contains a next pointer, which should be set to point to its immediate right neighbor at the same level. If there is no right neighbor, the next pointer should be set to null.

The function signature is typically: Node connect(Node root). You must connect all nodes' next pointers accordingly and return the root of the tree.

• You must use only constant extra space (excluding recursion stack).
• Do not use additional data structures like queues or lists for level order traversal.
• Assume the tree is non-empty and perfect (all leaves are at the same level, every parent has two children).

Thought Process

At first glance, the problem looks similar to a level order traversal where you visit nodes level by level. The brute-force solution would be to use a queue to traverse each level and connect the next pointers. However, the requirement to use constant extra space rules out such approaches.

The key insight is that since the tree is perfect, all nodes at a given level have children, and the structure is highly regular. This allows us to traverse the tree level by level using already established next pointers, without needing extra data structures.

We can use the leftmost node of each level to start traversing that level, and then connect the children of each node as we move along the level. This way, we only use a few pointers and no additional memory.

Solution Approach

• Step 1: Start from the root node. The root is the leftmost node of the first level.
• Step 2: For each level, use a pointer (head) to traverse nodes horizontally using their already established next pointers.
• Step 3: For each node at the current level:
  • Connect its left child's next to its right child.
  • If the node has a next (i.e., it's not the last node in the level), connect its right child's next to the left child of the node's next neighbor.
• Step 4: After finishing one level, move down to the leftmost node of the next level and repeat the process until you reach the leaves.
• Design Justification: We do not use any extra data structures. The traversal uses only a few pointers, and the perfect binary tree property guarantees that all nodes have both left and right children (except leaves).

Example Walkthrough

Consider the following perfect binary tree:

        1
      /   \
     2     3
    / \   / \
   4  5  6   7
  

• Level 1: Node 1 is the only node. Its next is null.
• Level 2:
  • Connect 2's next to 3.
  • Connect 3's next to null.
• Level 3:
  • Connect 4's next to 5.
  • Connect 5's next to 6 (because 5 is the right child of 2, and 2's next is 3, so 5's next is 3's left child).
  • Connect 6's next to 7.
  • Connect 7's next to null.

After running the algorithm, all next pointers are properly set, and you can traverse each level using these pointers.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(N), where N is the number of nodes (since each node is visited once).
  • Space Complexity: O(N), due to the use of a queue for level order traversal.
• Optimized approach (used above):
  • Time Complexity: O(N). Each node is visited and its pointers are set once.
  • Space Complexity: O(1). Only a few pointers are used, regardless of the tree size. The recursion stack is not used in this iterative solution.

The optimized approach is both time and space efficient, meeting the problem's constraints.

Summary

By leveraging the perfect binary tree structure, we can connect all next pointers using only constant extra space. The key is to traverse each level using already established next pointers, connecting children as we go. This results in an elegant, efficient solution that avoids extra data structures and meets all problem constraints.