[Leetcode] 116. Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect 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: []

Constraints:

The number of nodes in the tree is in the range [0, 2``12`` - 1].

-1000 <= Node.val <= 1000

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.

How to understand?

This given binary tree is perfect, so each node has its value, left child, right child, and next value. So the next value should points to the right next node in the same row(level). It's all set as Null value when it's given. Find the node's next value.

How to approach?

Level order traversal (BFS, Queue)

function connect(root: Node | null): Node | null {
    if (root == null) {
        return root;
    }
    let Q: Node[] = [];
    Q.push(root);
    while (Q.length > 0) {
        let size = Q.length;
        for (let i = 0; i < size; i++) {
            let node = Q.shift();
            if (i < size - 1) {
                node.next = Q[0];
            }
            if (node.left != null) {
                Q.push(node.left);
            }
            if (node.right != null) {
                Q.push(node.right);
            }
        }
    }
    return root;
}

create queue which has Node array in it.

and push the root for the first element.

when queue has length, use while condition to check the elements.

set the size initially as queue's length.

and then create for loop to examine all the elements in the queue range of 0 to size.

set the node as the first element in the current queue using shift method.

the current iteration's index is less than size-1 then set the .next as the queue's first element.

if it's more than size-1 then it means the element is the last element in the row. so no modification is required.

and next to if condition to check the left and right children and push them into the queue.

lastly return the modified root.

Using previously established next pointers

function connect(root: TreeNodeWithNext | null): TreeNodeWithNext | null {
    if (root == null) {
        return root;
    }
    let leftmost: TreeNodeWithNext | null = root;
    while (leftmost!.left != null) {
        let head: TreeNodeWithNext | null = 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;
}

create leftmost and store the root as start point.

while condition to check leftmost has left child.

in the while condition, set the head as the leftmost element.

and another while condition to check the head is not null.

then set the head's left's next as head's right, this means it shares the same parent.

if condition to check the current head's next is not null.

if it is true then it means it has the previously established next pointers, so we can use the N+1 level children value as .next value.

set current head's right's next as current head's next's left value.

and then move the head to the right side, set head as head.next.

in the outer while loop, the leftmost value will be set as leftmost's left value.

lastly return the modified root.