[Leetcode] 117. Populating Next Right Pointers in Each Node II

117. Populating Next Right Pointers in Each Node II

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.

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: []

Constraints:

The number of nodes in the tree is in the range [0, 6000].

-100 <= Node.val <= 100

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?

When the given binary tree is not a perfect binary tree, fill the node.next as the right side node of the each node on the same level. All the .next are initialised as Null.

How to approach?

Level order traversal

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

create queue array to store the nodes.

firstly, push the root to the queue.

and create the while condition to check the queue is not empty.

set the size as queue's length.

create for loop to iterate the range of 0 to size.

pop the first element in the queue and set it as node.

create the if condition to check if the i is less than size-1 since it means when it it same as size-1 or bigger than that it exceeds over the size. so it's not on the same row.

and 2 if conditions to check the child of current node and push it to the queue.

lastly return the modified root.

Previously established next pointers

function connect(root: Node | null): Node | null {
    let leftmost: Node | null = root;

    while (leftmost) {
        let cur: Node | null = leftmost;
        leftmost = null;
        let pre: Node | null = null;

        while (cur) {
            if (cur.left) {
                if (!leftmost) {
                    leftmost = cur.left;
                }

                if (pre) {
                    pre.next = cur.left;
                }

                pre = cur.left;
            }

            if (cur.right) {
                if (!leftmost) {
                    leftmost = cur.right;
                }

                if (pre) {
                    pre.next = cur.right;
                }

                pre = cur.right;
            }

            cur = cur.next;
        }
    }

    return root;
}

use leftmost, current, and prev variables to track the current row and N+1 row at the same time.

set leftmost as root.

create while condition to check the leftmost is not null.

set current as leftmost and reset it as null right away.

and set prev as null.

while condition to check the current is not null and check current.left and current.right in order.

lastly check the current as current.next that means it moves the pointer to the right side node in the same row.

when current.left child exists, check leftmost first and if it is null then set it as current.left, when prev does exist then set prev.next as current.left as well.

lastly set prev as current.left.

do the same thing on current.right child

This process is updating N+1 pointer to the right side while checking left child and then right child.

lastly return the updated root.