Populating Next Right Pointers in Each Node

Imagine a perfect binary tree where each node has a next pointer. Your task is to populate this next pointer for each node so that it points to the node immediately to its right on the same level. If there is no node to its right, the next pointer should be null. This is a common operation in tree traversals and data structure manipulation.

Problem Description

Given a perfect binary tree, where each node has a left child, a right child, and a next pointer. You need to connect each node to its "next" neighbor on the same level.

Key Requirements:

• The next pointer of a node should point to its immediate right sibling at the same level.
• The next pointer of the rightmost node at each level should be null.
• The tree is guaranteed to be a perfect binary tree. This means every non-leaf node has exactly two children, and all leaves are at the same depth.

Expected Behavior:

The algorithm should modify the next pointers of the existing tree structure. It should not create new nodes or return a new tree.

Important Edge Cases:

• An empty tree (root is null).
• A tree with only a root node.

Examples

Example 1:

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

(Here, the 'next' pointers are initially null for all nodes)

Output:
    1 -> NULL
   / \
  2 -> 3 -> NULL
 / \ / \
4->5->6->7 -> NULL

(Arrows indicate the 'next' pointers)

Explanation: Node 1's next is null. Node 2's next is Node 3. Node 3's next is null. Node 4's next is Node 5. Node 5's next is Node 6. Node 6's next is Node 7. Node 7's next is null.

Example 2:

Input:
    1

(A single node tree)

Output:
    1 -> NULL

Explanation: The root node is the only node, so its next pointer should be null.

Example 3:

Input:
    1
   / \
  2   3

(A tree with two levels)

Output:
    1 -> NULL
   / \
  2 -> 3 -> NULL

Explanation: Node 1's next is null. Node 2's next is Node 3. Node 3's next is null.

Constraints

• The number of nodes in the tree is between 0 and 2000.
• The value of each node is between -1000 and 1000.
• The tree is a perfect binary tree.
• The solution should aim for optimal time and space complexity.

Notes

• You will be provided with a Node structure that typically looks like this (conceptually):

  class Node {
      int val;
      Node left;
      Node right;
      Node next; // This is the pointer you need to populate
  }
  

• Consider how you might traverse the tree level by level.

• Can you leverage the next pointers of a parent level to populate the next pointers of the child level?

• Think about the space complexity. Can you solve this without using excessive extra space?