Statement▼
Given the root of a next
, connect all nodes from left to right. Do so in such a way that the next
pointer of each node points to its immediate right sibling except for the rightmost node, which points to the first node of the next level.
The next
pointer of the last node of the binary tree (i.e., the rightmost node of the last level) should be set to NULL.
Constraints:
The number of nodes in the tree is in the range
[0,500] .−1000≤ Node.data
≤1000
Solution
The algorithm connects all nodes by utilizing the structure of the perfect binary tree, where each non-leaf node has exactly two children. Using this property, the algorithm connects nodes without needing extra space. It uses two pointers: one to traverse the current level and another to connect nodes at the next level. Starting from the root, the algorithm links each node’s left child to its right child and then connects the right child to the next node’s left child on the same level, continuing this process across all nodes at that level. If no adjacent node is on the same level, the right child’s next
pointer is connected to the first node on the next lower level. This process continues until all nodes are connected in a manner that reflects level-order traversal.
The steps of the algorithm are given below:
If the root is
None
, the tree is empty. In this case, return immediately.Initialize two pointers
current
andlast
to the root node. Thecurrent
pointer traverses the nodes level by level, while thelast
keeps track of the last node connected via the next pointer.The loop continues as long as
current.left
exists. In a perfect binary tree, all non-leaf nodes have a left child, so this condition ensures that the loop continues until all levels are processed.First connection:
last.next = current.left
connects thelast
node (initially theroot
) to thecurrent.left
child. After this,last
is updated tocurrent.left
.Second connection:
last.next = current.right
connectscurrent.left
(now pointed to bylast
) tocurrent.right
.last
is then updated tocurrent.right
.Move to the next node:
current = current.next
moves thecurrent
pointer to the next node.
Finally, return the modified
root
of the tree, where all nodes are connected to their next sibling in the level-order traversal.
Let’s look at the following illustration to get a better understanding of the solution: