117. Populating Next Right Pointers in Each Node II

MediumTreeDepth-First SearchBreadth-First SearchLinked ListBinary Tree
Leetcode Link

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.

Learn more about Tree, Depth-First Search, Breadth-First Search, Linked List and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

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.

Solution Implementation

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
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
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
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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

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).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

The three-steps of Depth First Search are:

  1. Identify states;
  2. Draw the state-space tree;
  3. DFS on the state-space tree.

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

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 ๐Ÿ‘จโ€๐Ÿซ