0116.md

116. Populating Next Right Pointers in Each Node

Level:

Topic:

Question

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:

Initially, all next pointers are set to NULL.

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.

Intuition

Iterative:

• use bfs level order traversal and connect the next pointer until sees the last node of the level

Recursive:

• good use of previously established linked list to connect the next level node

Iterative Optimised:

• similiar to recursive

Code

Time: O(n)
Space: O(1)

Optimised

public Node connect(Node root) {
    if (root == null)
        return root;

    // this is gonna be the leftmost node of every level
    // connect next level's nodes from the current level
    Node leftmost = root;
    while (leftmost.left != null) {

        // traverse as a linked list
        Node head = leftmost;
        while (head != null) {

            // connect left -> right
            head.left.next = head.right;
            // connect right -> head.next.left
            if (head.next != null)
                head.right.next = head.next.left;

            head = head.next;
        }

        // the leftmost's left is gonna be the first node of the next level
        leftmost = leftmost.left;
    }
    return root;
}

Time: O(n)
Space: O(n)

Iterative

public Node connect(Node root) {
    Queue<Node> queue = new LinkedList<>();
    if (root != null)
        queue.add(root);

    Node curr = root;
    while (!queue.isEmpty()) {
        int n = queue.size();
        while (n-- > 0) {
            curr = queue.poll();
            if (n > 0)
                curr.next = queue.peek();

            if (curr.left != null)
                queue.add(curr.left);
            if (curr.right != null)
                queue.add(curr.right);
        }
    }

    return root;
}

Recursive

public Node connect(Node root) {
    helper(root);
    return root;
}

private void helper(Node root) {
    if (root == null)
        return;

    if (root.left != null && root.right != null) {
        root.left.next = root.right;
        if (root.next != null)
            root.right.next = root.next.left;
    }

    helper(root.left);
    helper(root.right);
}