117. Populating Next Right Pointers in Each Node II


Problem Description

In this LeetCode problem, we are given a binary tree where each node has an additional pointer called next. This tree structure is different from the standard binary tree structure, which typically only includes left and right pointers to represent the node's children. The next pointer in each node should be used to point to its immediate right neighbor on the same level. If no such neighbor exists, the next pointer should be set to NULL.

To clarify, if we imagine the nodes being aligned at each level from left to right, the next pointer of a node should reference the adjacent node to the right within the same level. For the rightmost nodes of each level, since there is no node to their right, their next pointer will remain NULL as initialized.

Initially, all the next pointers of the nodes in the tree are set to NULL. Our task is to modify the tree such that all next pointers are correctly assigned according to the problem's rules.

Intuition

The solution involves a level-order traversal (BFS-like approach) of the binary tree, where we iterate through nodes level by level. Since we need to connect nodes on the same level from left to right, we keep track of the first node on the new level that we visit while still iterating on the current level. This way, we have a reference when we need to move down a level.

To solve this, we need variables to keep track of:

  1. The previous node on the current level (prev), so we can set its next pointer to the current node.
  2. The first node on the next level (next), which is where we will move after finishing the current level.
  3. The current node that we're attaching to the next pointer of the previous node (curr).

A helper function modify takes care of the linking process, linking the current node to the previous one if it exists, and also updating the next variable to point to the first node at the next lower level when moving down the tree.

We use a while loop to navigate through the levels, and inside the loop, we traverse the current level using the next pointers (which are already pointing to the right or are NULL for the rightmost nodes). As we go, we use the modify helper function to link the children of the current node properly. We then transition down to the next level of the tree using the next variable, which we've already set to the first node on that level.

The traversal repeats until there are no more levels to process (i.e., when we've processed the rightmost node at the lowest level of the tree), ensuring that all next pointers are appropriately linked.

Solution Approach

The implementation for this problem involves a clever usage of pointers to traverse the binary tree level by level without using additional data structures like queues, which are commonly used for level-order traversal. Here's a step-by-step walkthrough of the process using the given Python code:

  1. Initialize Pointers: We start by creating a node pointer that points to the root of the tree. The loop that follows will process one level at a time. Two additional pointers, prev and next, are used to track the previous node and the first node on the next level, respectively.

  2. Outer While Loop: The outer loop continues until node is None. This loop ensures that we visit all the levels of the binary tree.

  3. Set Level Pointers: At the beginning of each iteration, we set prev and next to None. Here, prev will hold the last node we visited on the current level, and next will be updated to point to the first node of the next level as soon as we encounter it.

  4. Inner While Loop: The inner loop processes each level. It continues while there is a node to process on the current level.

  5. Helper Function - modify: Each iteration within the inner while loop calls the modify function with the node.left and node.right children. This function does three things:

    • Checks if the current child curr is None. If it is, we don't have anything to modify or link, so we return immediately.
    • The first non-None child encountered will be the starting node for the next level, and we update next to point to this child.
    • If there's a prev node, we link its next pointer to the current child, curr. This connects the previous child on the same level to the current one.
    • Assigns curr to prev because for the next child, curr will be the previous node.
  6. Traverse Current Level: After the children of the current node are processed, we move to the next node on the same level by updating node = node.next.

  7. Move to Next Level: Once the inner loop is done, we have processed all nodes on the current level, and next points to the first node of the next level. We set node = next to move down the tree and begin processing the next level.

  8. Return Modified Tree: The process continues until all nodes have been processed. The outer loop ends, and the original root, which now has all its next pointers correctly set, is returned.

Throughout the process, we are effectively doing a BFS traversal without an auxiliary queue, using next pointers to navigate through the tree instead. The solution leverages the fact that we can link the next level's nodes while we are still on the current level, using the next pointers that we're setting along the way.

💪
Level Up Your
Algo Skills

Example Walkthrough

To illustrate the solution approach, consider a binary tree with the following structure:

1        1
2       / \
3      2   3
4     / \   \
5    4   5   7

We start by initiating a variable node to point to the root of the tree, in this case, the node with value 1. The variables prev and next are initialized to None. The outer while loop starts, indicating we're beginning with the top level of the tree.

  • At the top level:

    • The inner while loop processes the top level.
    • The modify helper function is called first with node.left (2) and then with node.right (3). Since prev is None, we just update next to node 2 (the first child of this level).
    • prev is then updated to 2.
    • We connect 2 to 3 by setting 2.next to 3 through the modify function with node.right.
    • Since node 3 is the rightmost node at this level, its next pointer is left as None.
    • Finally, the inner loop concludes, as there are no more nodes on the top level.
  • We switch levels by setting node to next, which is node 2, and prev and next to None.

  • At the second level:

    • We start with node 2. Again, the inner loop processes the level.
    • The modify function is called first with node.left (4) and then with node.right (5). next is updated to 4, and prev to 4.
    • prev (4) is connected to 5 via 5's next pointer because 5 is node.right of 2.
    • On to node 3, its children are None and 7. So, modify skips the None child, and connects 5 (the prev) to 7, since 7 is node.right of 3.
    • The rightmost nodes (5 and 7) have their next pointers already as None, and they stay that way since there are no more nodes to their right.
    • After finishing node 3, the inner loop concludes, as there are no more nodes at this level with a non-NULL next pointer.
  • We again switch levels by setting node to next, which is node 4. However, nodes 4, 5, and 7 have no children, so subsequent iterations of the outer loop will not modify any next pointers.

After the outer while loop exits, we have successfully connected all the next pointers:

1        1 -> NULL
2       / \
3      2 -> 3 -> NULL
4     / \    \
5    4 ->5 -> 7 -> NULL

The tree's next pointers have been set up to link nodes together across each level from left to right, with the rightmost nodes pointing to NULL, as required by the problem. All the intended connections have been made while respecting the binary tree structure and the rule stating that only immediate right neighbors should be linked. The solution also ensures that no additional data structures are used by leveraging the next pointers and processing the tree level by level.

Python Solution

1"""
2# Definition for a Node.
3class Node:
4    def __init__(self, val:int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
5        self.val = val
6        self.left = left
7        self.right = right
8        self.next = next
9"""
10
11class Solution:
12    def connect(self, root: 'Node') -> 'Node':
13        # Helper function to connect nodes at the same level.
14        def connect_nodes(curr: 'Node'):
15            nonlocal previous_node, next_start_node
16            if curr is None:
17                return
18            # Initialize the start of the next level if it hasn't been set yet.
19            next_start_node = next_start_node or curr
20            # If there is a previous node on the same level, link it to the current node.
21            if previous_node:
22                previous_node.next = curr
23            # Update the previous_node to the current one for the next iteration.
24            previous_node = curr
25
26        current_node = root
27        # Iterate through the levels of the tree.
28        while current_node:
29            # Reset previous_node and next_start_node for the next level.
30            previous_node = next_start_node = None
31            # Iterate nodes in the current level and connect child nodes.
32            while current_node:
33                connect_nodes(current_node.left)
34                connect_nodes(current_node.right)
35                # Move to the next node in the current level.
36                current_node = current_node.next
37            # Proceed to the next level.
38            current_node = next_start_node
39      
40        # Return the root with updated next pointers.
41        return root
42

Java Solution

1class Solution {
2
3    // Class-level variables to hold the previous node and
4    // the next level's start node
5    private Node previous;
6    private Node nextLevelStart;
7
8    public Node connect(Node root) {
9        Node currentLevelNode = root;
10
11        // Outer loop: Traverse levels of the tree
12        while (currentLevelNode != null) {
13            // Reset previous and nextLevelStart pointers when moving to a new level
14            previous = null;
15            nextLevelStart = null;
16
17            // Inner loop: Traverse nodes within the current level
18            while (currentLevelNode != null) {
19                // Modify the left child pointer
20                modifyPointer(currentLevelNode.left);
21                // Modify the right child pointer
22                modifyPointer(currentLevelNode.right);
23
24                // Move to the next node in the current level
25                currentLevelNode = currentLevelNode.next;
26            }
27
28            // Proceed to the next level
29            currentLevelNode = nextLevelStart;
30        }
31
32        // Return the modified tree's root
33        return root;
34    }
35
36    // Helper function to connect child nodes at the current level
37    private void modifyPointer(Node currentNode) {
38        if (currentNode == null) {
39            // If current node is null, do nothing
40            return;
41        }
42
43        // If this is the first node of the next level,
44        // update the nextLevelStart pointer
45        if (nextLevelStart == null) {
46            nextLevelStart = currentNode;
47        }
48
49        // If a previous node was found, link the previous node's next pointer
50        // to the current node
51        if (previous != null) {
52            previous.next = currentNode;
53        }
54
55        // Update the previous pointer to the current node
56        previous = currentNode;
57    }
58}
59

C++ Solution

1class Solution {
2public:
3    Node* connect(Node* root) {
4        Node* currentNode = root; // Start with the root of the tree
5        Node* previousNode = nullptr; // This will keep track of the previous node on the current level
6        Node* nextLevelStart = nullptr; // This will point to the first node of the next level
7
8        // Lambda function to connect nodes at the same level
9        auto connectNodes = [&](Node* childNode) {
10            if (!childNode) {
11                return; // If the child node is null, no connection can be made
12            }
13            if (!nextLevelStart) {
14                nextLevelStart = childNode; // Set the start of the next level, if it hasn't been set
15            }
16            if (previousNode) {
17                previousNode->next = childNode; // Connect the previous node to the current child node
18            }
19            previousNode = childNode; // Current child node becomes the previous node for the next iteration
20        };
21
22        // Traverse the tree by level
23        while (currentNode) {
24            previousNode = nextLevelStart = nullptr; // Reset pointers for each level
25
26            // Connect children nodes within the current level
27            while (currentNode) {
28                connectNodes(currentNode->left);  // Connect left child if it exists
29                connectNodes(currentNode->right); // Connect right child if it exists
30                currentNode = currentNode->next;  // Move to the next node at the same level
31            }
32
33            currentNode = nextLevelStart; // Move down to the start of the next level
34        }
35
36        return root; // Return the modified tree with next pointers connected
37    }
38};
39

Typescript Solution

1// Definition for a Node.
2class Node {
3    val: number;
4    left: Node | null;
5    right: Node | null;
6    next: Node | null;
7
8    constructor(val?: number, left?: Node, right?: Node, next?: Node) {
9        this.val = val === undefined ? 0 : val;
10        this.left = left === undefined ? null : left;
11        this.right = right === undefined ? null : right;
12        this.next = next === undefined ? null : next;
13    }
14}
15
16// This function connects each node on the same level with the following node 
17// (to its right) in a binary tree and returns the root of the tree. It uses a 
18// level order traversal method utilizing a queue to process nodes level by level.
19function connect(root: Node | null): Node | null {
20    // If the root is null, the tree is empty; thus return the root as is.
21    if (root === null) {
22        return root;
23    }
24
25    // Initialize the queue with the root of the tree.
26    const queue: Node[] = [root];
27
28    while (queue.length > 0) {
29        // Number of nodes at the current level.
30        const levelSize = queue.length;
31
32        // Variable to keep track of the previous node to set the next pointer.
33        let previousNode: Node | null = null;
34
35        // Loop through each node on the current level.
36        for (let i = 0; i < levelSize; i++) {
37            // Retrieve and remove the first node from the queue.
38            const currentNode = queue.shift()!;
39
40            // If there was a previous node in this level, connect its next to the current node.
41            if (previousNode !== null) {
42                previousNode.next = currentNode;
43            }
44
45            // The current node will be the previous one when the for loop processes the next node.
46            previousNode = currentNode;
47
48            // If the current node has a left child, add it to the queue.
49            if (currentNode.left) {
50                queue.push(currentNode.left);
51            }
52
53            // If the current node has a right child, add it to the queue.
54            if (currentNode.right) {
55                queue.push(currentNode.right);
56            }
57        }
58
59        // After the level is processed, the last node should point to null, which is already the default.
60    }
61
62    // After connecting all levels, return the root node of the tree.
63    return root;
64}
65

Time and Space Complexity

The given code is designed to connect each node to its next right node in a binary tree, making use of level order traversal.

Time Complexity:

The time complexity of the code is O(N) where N is the number of nodes in the binary tree. This is because the algorithm visits each node exactly once. During each visit, it only performs constant time operations such as setting the next pointer.

Each level of the tree is examined using a while loop which iterates through the nodes that are horizontally connected via the next pointer. For each node, it calls the modify function twice—once for the left child and once for the right child. However, these calls do not result in recursive function calls that would amplify the runtime since they only alter pointers if the children are not null.

Space Complexity:

The space complexity of the code is O(1) assuming that function call stack space isn't considered for the space complexity (as is common for such analysis). This is because the algorithm uses only a constant amount of extra space: a few pointers (curr, prev, next) to keep track of the current node and to link the next level nodes. It does not allocate any additional data structures that grow with the size of the input tree.

However, if we do consider recursive call stack then the space complexity would be O(H) where H is the height of the tree. This accounts for the call stack during the execution of the function when called recursively for each level of the tree. For a balanced binary tree, this would be O(log N), and for a completely unbalanced tree, it could be O(N) in the worst case. The provided code does not seem to use recursion, so the space complexity remains O(1).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫