116. Populating Next Right Pointers in Each Node
Problem Description
In this problem, we are dealing with a perfect binary tree where all leaves are at the same level, and every parent node has exactly two children. Each node in the tree has an additional pointer called next
in addition to the usual left
and right
child pointers. Initially, all next
pointers are set to NULL
. The goal is to modify the tree such that each node’s next
pointer points to the following node on the same level. For the nodes at the far right of each level, since there is no next right node, their next
pointer should remain set to NULL
.
Flowchart Walkthrough
Let's use the algorithm flowchart to determine the most appropriate method for solving LeetCode 116. Populating Next Right Pointers in Each Node. Here is the step-by-step analysis:
Is it a graph?
- Yes: The binary tree can be conceptualized as a graph where nodes are connected vertically (parent to child) and now horizontally due to the next pointers.
Is it a tree?
- Yes: The data structure used in the problem is specifically mentioned as a "Perfect Binary Tree".
Is it a problem related to directed acyclic graphs (DAGs)?
- No: Although a tree is technically a DAG, the primary focus here isn't on aspects typical to DAGs like topological sorting.
Is the problem related to shortest paths?
- No: The objective is to populate next right pointers, not to find a shortest path.
Does the problem involve connectivity?
- No: While trees inherently involve connectivity (nodes connected to their children), this problem specifically focuses on modifying node pointers horizontally rather than exploring or validating node connectivity.
Does the problem have small constraints?
- Yes: The tree is perfect and binary, which implies more controlled growth and can often be handled efficiently with depth-first search or recursive strategies due to its predictable pattern (each level fully populated).
Conclusion: Given it's a tree and we want to manipulate node relationships rather at a deeper (or recursive) level in the context of established tree paths while dealing with fairly manageable constraints, the flowchart suggests that Depth-First Search (DFS) or a recursive approach is suitable for efficiently visiting and modifying each node to point to its next right node.
Intuition
The solution approach is based on a level-order traversal (also known as a breadth-first search) of the tree. Since we're dealing with a perfect binary tree, every level is fully filled, and therefore the problem simplifies to connecting all nodes at each level in a left-to-right manner.
Here is the intuition step by step:
- We initialize a queue that will store nodes at the current level we're processing.
- We begin traversal with the root node by adding it into the queue.
- We start a loop that will continue until the queue is empty, which means there are no more levels to process.
- Inside this loop, we initialize a variable
p
toNone
, to keep track of the previous node as we process. - We then process nodes level by level:
- At the start of a level, we record the number of nodes at that level (the queue’s length) to ensure we only process those nodes before moving to the next level.
- We pop nodes off of the queue left to right, and for each node:
a. If
p
is notNULL
(this is not the first node of the level), we set p'snext
to the current node. b. We then updatep
to the current node. c. We add the current node's left and right children to the queue.
- By the end of the loop, all
next
pointers should accurately point to the next right node, or remainNULL
if it's the far-right node of that level. - Finally, we return the modified tree starting with the root node.
The given solution ensures that each node at a given level points to its adjacent node on the right before descending to the next level. It takes advantage of the queue data structure for keeping track of nodes level by level and updates the next
pointers in a systematic manner.
Learn more about Tree, Depth-First Search, Breadth-First Search, Linked List and Binary Tree patterns.
Solution Approach
The implementation of the solution is primarily based on the Breadth-First Search (BFS) algorithm, which is a common way to traverse trees level by level. To make this possible, we employ a queue data structure, which will hold the nodes of the tree according to the BFS traversal order. The Python deque
from the collections
module is used for the queue because it allows for fast and efficient appending and popping of elements from both ends.
Here is a breakdown of the implementation steps, referring to the data structures and patterns used:
- We first check if the root is
None
. If it is, we returnNone
as there is nothing to connect. - We initialize a queue
q
with the root node of the tree. - We enter a while loop that will run as long as there are elements in the queue.
- In each iteration of the while loop, we first initialize a variable
p
toNone
, which will serve as a pointer to the previous node at the current level. - We determine the number of nodes at the current level of the tree by examining the length of the queue using
len(q)
. - We then use a for loop to iterate over all nodes at the current level:
- We use
q.popleft()
to remove and obtain the first node from the queue. - We check if
p
is notNone
. This implies that this is not the first node at the current level, so we set thenext
ofp
to the current node. - We set
p
to the current node after updating itsnext
. - If the current node has a left child, we append it to the queue, and similarly, if it has a right child, we append it to the queue.
- We use
- Finally, once the while loop finishes executing, all nodes'
next
pointers have been properly set, and we return theroot
of the updated tree.
This solution utilizes the properties of a perfect binary tree and a level-order traversal algorithm to connect the nodes at each level efficiently. With the help of the queue, we are able to process nodes in the correct order and update their next
pointers while traversing the tree.
Here's a snippet of the key part of the implementation that demonstrates the core process:
while q:
p = None
for _ in range(len(q)):
node = q.popleft()
if p:
p.next = node
p = node
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
In this snippet, the loop structures and the assignments are critical in understanding how the connections (based on next
pointers) are made between nodes at the same level.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example of a perfect binary tree to illustrate the solution approach. Our example tree is as follows (represented as levels):
1 / \ 2 3 / \ / \ 4 5 6 7
To begin, here is an outline of the steps we’ll follow to execute the algorithm described:
- Create an empty queue (will use a deque for efficiency) and enqueue the root node (node 1).
- Process the nodes until the queue is empty.
Now let's walkthrough each level:
-
Level 0: Tree root (Node 1)
- Initialize
queue
as deque([1]). p = None
- There is only one node at this level, so we don't have to set any
next
pointers. - Enqueue its children,
queue
becomes deque([2, 3]).
- Initialize
-
Level 1: Nodes 2 and 3
p = None
, we then dequeue node 2 and sincep
isNone
,next
is not set.p
is updated to node 2. Node 2’s children (4, 5) are enqueued,queue
becomes deque([3, 4, 5]).- We dequeue node 3, and set
next
of node 2 to node 3 (p.next = node
),p
is updated to node 3. - Node 3's children (6, 7) are enqueued,
queue
becomes deque([4, 5, 6, 7]).
-
Level 2: Nodes 4, 5, 6, and 7
p = None
, we then dequeue node 4 and sincep
isNone
,next
is not set.p
is updated to node 4.- Continue with nodes 5, 6, and 7 in the same way, dequeuing each node, setting its
next
pointer to the subsequent node, and updatingp
to the latest node. - After node 7, the
queue
is empty, and thenext
pointer is not updated as it is the last node at this level.
At the end of this process, here’s how the next
pointers would be set:
1 -> NULL / \ 2 -> 3 -> NULL / \ / \ 4->5->6->7 -> NULL
All the next
pointers at the same level have been connected, and the next
pointers of the last nodes at each level remain pointing to NULL
, signifying the end of the level. This completes the walk through of the tree using the given solution approach.
Solution Implementation
1from collections import deque # Importing deque from collections module for queue functionality
2
3class Node:
4 """ Definition for a binary tree node with a next pointer. """
5 def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
6 self.val = val
7 self.left = left
8 self.right = right
9 self.next = next
10
11class Solution:
12 def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
13 """
14 Connects each node to its next right node in a binary tree.
15 It is perfect binary tree which means all leaves are on the same level,
16 and every parent has two children. The next pointer of the last node in
17 each level is set to None.
18
19 :param root: The root of the binary tree.
20 :type root: Optional[Node]
21 :return: The root of the binary tree with next pointers set.
22 :rtype: Optional[Node]
23 """
24 if root is None: # If the tree is empty, return the empty root
25 return root
26
27 queue = deque([root]) # Initialize queue with the root node
28 while queue:
29 previous_node = None # Initialize previous node as None
30 level_size = len(queue) # Current level's size in the binary tree
31
32 for _ in range(level_size): # Traverse all nodes at the current level
33 node = queue.popleft() # Remove the node from the queue
34 if previous_node: # If there is a previous node, set its next pointer to the current node
35 previous_node.next = node
36 previous_node = node # Update previous node to the current node
37
38 # Add left and right children to the queue if they exist
39 if node.left:
40 queue.append(node.left)
41 if node.right:
42 queue.append(node.right)
43
44 # At the end of the level, previous_node is the last node and its next should already be None
45
46 return root # Return the modified tree root with next pointers connected
47
1// Definition for a binary tree node with a next pointer.
2class Node {
3 public int val;
4 public Node left;
5 public Node right;
6 public Node next;
7
8 public Node() {}
9
10 public Node(int _val) {
11 val = _val;
12 }
13
14 public Node(int _val, Node _left, Node _right, Node _next) {
15 val = _val;
16 left = _left;
17 right = _right;
18 next = _next;
19 }
20}
21
22class Solution {
23 // Method connects each node to its next right node in the same level.
24 // If there is no next right node, the next pointer should be set to NULL.
25 public Node connect(Node root) {
26 // Handle the base case when the tree is empty.
27 if (root == null) {
28 return root;
29 }
30
31 // Queue to hold the nodes to be processed.
32 Deque<Node> queue = new ArrayDeque<>();
33 // Start with the root node.
34 queue.offer(root);
35
36 // Traverse the binary tree level by level.
37 while (!queue.isEmpty()) {
38 // Previous node on the current level.
39 Node previousNode = null;
40
41 // Process all nodes in the current level.
42 for (int i = queue.size(); i > 0; --i) {
43 // Get the next node from the queue.
44 Node currentNode = queue.poll();
45
46 // Link the previous node (if any) to the current one.
47 if (previousNode != null) {
48 previousNode.next = currentNode;
49 }
50 // Current node becomes the previous node for the next iteration.
51 previousNode = currentNode;
52
53 // Add the children of current node to the queue for next level processing.
54 if (currentNode.left != null) {
55 queue.offer(currentNode.left);
56 }
57 if (currentNode.right != null) {
58 queue.offer(currentNode.right);
59 }
60 }
61 }
62
63 // Return the root of the modified tree.
64 return root;
65 }
66}
67
1class Solution {
2public:
3 // Connects all nodes at the same level in a binary tree using 'next' pointers.
4 Node* connect(Node* root) {
5 // If the tree is empty, return the root directly.
6 if (!root) {
7 return root;
8 }
9
10 // Initialize the queue with the root of the tree.
11 queue<Node*> nodesQueue;
12 nodesQueue.push(root);
13
14 // Process nodes level by level.
15 while (!nodesQueue.empty()) {
16 // The previous node at the current level, initialized as nullptr.
17 Node* prevNode = nullptr;
18
19 // Number of nodes at the current level.
20 int levelNodeCount = nodesQueue.size();
21
22 // Iterate over all nodes in the current level.
23 for (int i = 0; i < levelNodeCount; ++i) {
24 // Retrieve and remove the node from the front of the queue.
25 Node* currentNode = nodesQueue.front();
26 nodesQueue.pop();
27
28 // Connect the previous node with the current node.
29 if (prevNode) {
30 prevNode->next = currentNode;
31 }
32 // Update the previous node to the current node.
33 prevNode = currentNode;
34
35 // Add the left child to the queue if it exists.
36 if (currentNode->left) {
37 nodesQueue.push(currentNode->left);
38 }
39 // Add the right child to the queue if it exists.
40 if (currentNode->right) {
41 nodesQueue.push(currentNode->right);
42 }
43 }
44 // The last node in the level points to nullptr, which is already the case.
45 }
46
47 // Return the updated tree root with all 'next' pointers set.
48 return root;
49 }
50};
51
1// TypeScript definition of the Node class structure
2interface INode {
3 val: number;
4 left: INode | null;
5 right: INode | null;
6 next: INode | null;
7}
8
9/**
10 * Connects each node to its next right node in a perfect binary tree.
11 * @param root - The root node of the binary tree.
12 * @returns The root node of the modified tree with connected next pointers.
13 */
14function connect(root: INode | null): INode | null {
15 // If the tree is empty or if it's a single node tree, return the root since there are no next pointers to set.
16 if (root === null || root.left === null) {
17 return root;
18 }
19
20 // Connect the left child's next pointer to the right child.
21 root.left.next = root.right;
22
23 // If next pointer is available for the current node, connect the current's right child to the next's left child.
24 if (root.next !== null) {
25 root.right.next = root.next.left;
26 }
27
28 // Recursively connect the left and right subtrees.
29 connect(root.left);
30 connect(root.right);
31
32 // Return the root node after completing the next pointer connections.
33 return root;
34}
35
Time and Space Complexity
Time Complexity
The time complexity of the code is O(N)
, where N
is the total number of nodes in the binary tree. The algorithm employs a breadth-first search approach, where each node is visited exactly once. Because we visit each node once and perform a constant amount of work for each node (like setting the next
pointers and pushing children to the queue), the overall time complexity is linear with respect to the number of nodes.
Space Complexity
The space complexity of the code is O(N)
. The space is mainly occupied by the queue q
, which in the worst-case scenario can contain all nodes at the deepest level of the binary tree. In a perfect binary tree, the last level could contain approximately N/2
nodes, where N
is the total number of nodes. Thus, the space complexity is proportional to the number of nodes in the bottom level of the tree, making it O(N)
in the worst case.
Learn more about how to find time and space complexity quickly using problem constraints.
Given a sorted array of integers and an integer called target, find the element that
equals to the target and return its index. Select the correct code that fills the
___
in the given code snippet.
1def binary_search(arr, target):
2 left, right = 0, len(arr) - 1
3 while left ___ right:
4 mid = (left + right) // 2
5 if arr[mid] == target:
6 return mid
7 if arr[mid] < target:
8 ___ = mid + 1
9 else:
10 ___ = mid - 1
11 return -1
12
1public static int binarySearch(int[] arr, int target) {
2 int left = 0;
3 int right = arr.length - 1;
4
5 while (left ___ right) {
6 int mid = left + (right - left) / 2;
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
1function binarySearch(arr, target) {
2 let left = 0;
3 let right = arr.length - 1;
4
5 while (left ___ right) {
6 let mid = left + Math.trunc((right - left) / 2);
7 if (arr[mid] == target) return mid;
8 if (arr[mid] < target) {
9 ___ = mid + 1;
10 } else {
11 ___ = mid - 1;
12 }
13 }
14 return -1;
15}
16
Recommended Readings
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
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
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
Want a Structured Path to Master System Design Too? Don’t Miss This!