116. Populating Next Right Pointers in Each Node.md

116. Populating Next Right Pointers in Each Node

Tag

• BFS, LevelOrder, Using Previous Pointers
• Amazon, Adobe, Microsoft

Description

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, 212 - 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.

Solution

My naive BFS solution

• A naive solution is to use BFS and link the nodes in the same level

class Solution {
    public Node connect(Node root) {
        // Use BFS for level order traversal
        // corner case
        if (root == null) {
            return null;
        }
        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            // Get the current layer and connect
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // Get cur node to operate
                Node cur = queue.poll();
                // Assign next
                if (i == size - 1) {
                    cur.next = null;
                } else {
                    cur.next = queue.peek();
                }
                // Offer cur's children
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
        }
        return root;
    }
}

TC: O(n)

SC: O(n)

---

Better solution for the follow-up: Link using the previous level

• When 2 nodes have the same parent, easy link ; when 2 nodes don't have same parent, link them using previously established parent.next

class Solution {
    public Node connect(Node root) {
        // corner case
        if (root == null) {
            return null;
        }
        // Init
        Node leftmost = root;
        // As long as we don't hit leaf, cuz we are operating cur node's children level
        while (leftmost.left != null) {
            // Declare a ref to operate cur layer's child
            Node cur = leftmost;
            while (cur != null) {
                // link nodes under same parent
                cur.left.next = cur.right;
                // link nodes under different parent
                if (cur.next != null) {
                    cur.right.next = cur.next.left;
                }
                // Update cur
                cur = cur.next;
            }
            // Proceed to next level
            leftmost = leftmost.left;
        }
        return root;
    }
}

TC: O(n)

SC: O(1)