5.13 Populating Next Right Pointers in Each Node

5.13.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 116
• Difficulty: Medium
• URL: https://leetcode.com/problems/populating-next-right-pointers-in-each-node/
• Tags:
• Techniques: Breadth First Search, Tree

5.13.2 Description

Connect each node’s next pointer to its right neighbor on the same level in a perfect binary tree.

5.13.3 Solution - Level Traversal

5.13.3.1 Walkthrough

Use the next pointers to traverse each level without a queue. For each node, connect left -> right, and if a next neighbor exists, connect right -> neighbor.left. Then advance to the leftmost node of the next level.

5.13.3.2 Analysis

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

5.13.3.3 Code - Java

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