LeetCode 116. Populating Next Right Pointers in Each Node Java Solution

Problem

Populating Next Right Pointers in Each Node - LeetCode

Approach

• Given a basic tree, the task is to connect its nodes.

• Essentially, we need an algorithm to traverse the tree in level order and connect each node accordingly.

  • The problem assumes a perfect binary tree, meaning there are no empty nodes.

  • At level 1, connect all nodes at level 2.

  • Set the level's leftmost node as levelStart.

  • Connect the next node with its sibling (since the upper level is already connected, moving is easy).

  • If the next node's left child does not exist, it means the current level is fully connected.

• BFS (level order) or recursive function can be used.

• Recursive functions are often used when they can simplify complex tasks. However, this problem only requires a simple level order traversal without the need for previous calculated values, making recursion unnecessary.

• Moreover, if the tree is large, there is a possibility of a stack overflow, so it's better to avoid recursion.

Github Link

https://github.com/eunhanlee/LeetCode_116_PopulatingNextRightPointersinEachNode_Solution.git

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

class Solution {
    /**
     * Connects each node of the given binary tree with its right pointer.
     *
     * @param root The root node of the binary tree
     * @return The root node of the connected binary tree
     */
    public Node connect(Node root) {
        if (root == null)
            return null;

        // The leftmost node of the level
        Node levelStart = root;

        while (levelStart.left != null) {
            // Current node
            Node curr = levelStart;

            while (curr != null) {
                // Set the left child's next pointer to the right child
                curr.left.next = curr.right;
                // Set the right child's next pointer to the left child of the next node
                if (curr.next != null) curr.right.next = curr.next.left;
                // Move to the next node in the same level
                curr = curr.next;
            }

            // Move to the leftmost node of the next level
            levelStart = levelStart.left;
        }

        return root;
    }
}