Populating Next Right Pointers in Each Node II
MedPrompt
Given a binary tree
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.
Initially, all next pointers are set to NULL.
Example 1:
Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.Example 2:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 6000]. -100 <= Node.val <= 100
Follow-up:
- You may only use constant extra space.
- The recursive approach is fine. You may assume implicit stack space does not count as extra space for this problem.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach uses a standard Breadth-First Search (BFS) to traverse the tree level by level. A queue is used to store the nodes of the current level. As we process each node, we connect it to the previously processed node on the same level.
Algorithm
- If the
rootisnull, there is nothing to connect, so returnnull. - Initialize a queue (e.g.,
LinkedList) and add therootnode to it. - Begin a loop that continues as long as the queue is not empty.
- At the start of each level, determine the number of nodes on that level by checking the current
queue.size(). Let's call thislevelSize. - Initialize a
prevnode pointer tonull. This pointer will keep track of the previous node processed on the current level. - Start an inner loop that runs
levelSizetimes to process each node of the current level. - Inside the inner loop, dequeue a node and call it
current. - If
previs notnull, it meanscurrentis not the first node on this level. Setprev.next = currentto link the previous node to the current one. - Update
prevto point tocurrent. - If
current.leftis notnull, enqueue it to be processed in the next level. - If
current.rightis notnull, enqueue it as well. - Once the inner loop completes, all nodes for the current level are connected. The outer loop then continues to the next level.
- After the outer loop finishes, return the
root.
Walkthrough
We can solve this problem by performing a level order traversal of the tree, which is naturally implemented using a queue. The core idea is to process nodes one level at a time. For each level, we iterate through all its nodes from left to right, keeping track of the previously visited node to establish the next connection.
By getting the size of the queue before processing a level, we know exactly how many nodes belong to that level. This allows us to correctly connect nodes within the same level and ensures the next pointer of the rightmost node of a level remains null.
/*// Definition for a Node.class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; }};*/ class Solution { public Node connect(Node root) { if (root == null) { return null; } Queue<Node> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int levelSize = queue.size(); Node prev = null; for (int i = 0; i < levelSize; i++) { Node current = queue.poll(); if (prev != null) { prev.next = current; } prev = current; if (current.left != null) { queue.offer(current.left); } if (current.right != null) { queue.offer(current.right); } } } return root; }}Complexity
Time
O(N)
Space
O(W)
Trade-offs
Pros
The logic is straightforward and follows the standard BFS pattern, making it easy to understand and implement.
It correctly handles any type of binary tree, not just perfect ones.
Cons
Violates the follow-up constraint of using only constant extra space.
The space usage can be substantial for very wide trees, potentially leading to memory issues.
This optimized approach avoids using a queue and instead utilizes the next pointers established in the previous level to traverse the current level. It iterates through the tree level by level, using pointers to keep track of the head of the current level and to build the connections for the next level.
Algorithm
- Initialize
levelHead = root. This pointer marks the start of the current level being processed. - Start an outer loop that continues as long as
levelHeadis notnull. - Inside the loop, create a
dummynode. This node'snextpointer will be used to build the linked list for the next level. Initialize anextLevelCurrpointer to thisdummynode. - Initialize a
currpointer tolevelHeadto iterate through the nodes of the current level using theirnextpointers. - Start an inner loop that continues as long as
curris notnull. - Inside the inner loop, check for children of the
currnode: a. Ifcurr.leftis notnull, append it to the next level's list:nextLevelCurr.next = curr.left, and then advance the pointer:nextLevelCurr = nextLevelCurr.next. b. Ifcurr.rightis notnull, do the same:nextLevelCurr.next = curr.right, andnextLevelCurr = nextLevelCurr.next. - Move to the next node on the current level:
curr = curr.next. - After the inner loop finishes, the
nextpointer of thedummynode (dummy.next) will point to the head of the now-connected next level. - Update
levelHeadtodummy.nextto move the processing to the next level. - Once the outer loop finishes, all levels have been processed. Return the original
root.
Walkthrough
This approach achieves the O(1) space complexity requirement by cleverly using the next pointers that are already established. We can think of the process as having a pointer, levelHead, that always points to the start of the current level. We then use another pointer, curr, to traverse this level from left to right using the next links.
As we traverse the current level, we establish the next connections for the level below it. To simplify linking the children, we use a dummy node. This dummy node acts as a sentinel, providing a fixed starting point for the linked list of the next level. A nextLevelCurr pointer starts at the dummy node and is used to append the children of the nodes from the current level.
After iterating through the entire current level, dummy.next will point to the first node of the next level. We then update levelHead to dummy.next and repeat the process for the subsequent level.
/*// Definition for a Node.class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; }};*/ class Solution { public Node connect(Node root) { Node levelHead = root; while (levelHead != null) { // Dummy node to anchor the start of the next level Node dummy = new Node(0); Node nextLevelCurr = dummy; Node curr = levelHead; // Iterate through the current level while (curr != null) { if (curr.left != null) { nextLevelCurr.next = curr.left; nextLevelCurr = nextLevelCurr.next; } if (curr.right != null) { nextLevelCurr.next = curr.right; nextLevelCurr = nextLevelCurr.next; } curr = curr.next; } // Move to the start of the next level levelHead = dummy.next; } return root; }}Complexity
Time
O(N)
Space
O(1)
Trade-offs
Pros
Achieves optimal O(1) extra space complexity, satisfying the follow-up constraint.
Maintains an efficient O(N) time complexity.
Cons
The logic is more complex than the BFS approach, involving multiple pointers and a dummy node, which can be harder to reason about initially.
Solutions
Solution
/* // Definition for a Node. public class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } } */ public class Solution { private Node prev , next ; public Node Connect ( Node root ) { Node node = root ; while ( node != null ) { prev = null ; next = null ; while ( node != null ) { modify ( node . left ); modify ( node . right ); node = node . next ; } node = next ; } return root ; } private void modify ( Node curr ) { if ( curr == null ) { return ; } if ( next == null ) { next = curr ; } if ( prev != null ) { prev . next = curr ; } prev = curr ; } }/* // Definition for a Node. class Node { public int val; public Node left; public Node right; public Node next; public Node() {} public Node(int _val) { val = _val; } public Node(int _val, Node _left, Node _right, Node _next) { val = _val; left = _left; right = _right; next = _next; } }; */ class Solution { private Node prev , next ; public Node connect ( Node root ) { Node node = root ; while ( node != null ) { prev = null ; next = null ; while ( node != null ) { modify ( node . left ); modify ( node . right ); node = node . next ; } node = next ; } return root ; } private void modify ( Node curr ) { if ( curr == null ) { return ; } if ( next == null ) { next = curr ; } if ( prev != null ) { prev . next = curr ; } prev = curr ; } }/* // Definition for a Node. class Node { public: int val; Node* left; Node* right; Node* next; Node() : val(0), left(NULL), right(NULL), next(NULL) {} Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {} Node(int _val, Node* _left, Node* _right, Node* _next) : val(_val), left(_left), right(_right), next(_next) {} }; */ class Solution { public: Node * connect ( Node * root ) { Node * node = root ; Node * prev = nullptr ; Node * next = nullptr ; auto modify = [ & ]( Node * curr ) { if ( ! curr ) { return ; } if ( ! next ) { next = curr ; } if ( prev ) { prev -> next = curr ; } prev = curr ; }; while ( node ) { prev = next = nullptr ; while ( node ) { modify ( node -> left ); modify ( node -> right ); node = node -> next ; } node = next ; } return root ; } };""" # Definition for a Node. class Node: def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None): self.val = val self.left = left self.right = right self.next = next """ class Solution : def connect ( self , root : "Node" ) -> "Node" : def modify ( curr ): nonlocal prev_node , next_node if curr is None : return if next_node is None : # next level's first node next_node = curr # "if next_node is None" logic can be replaced by: # next_node = next_node or curr if prev_node : prev_node . next = curr prev_node = curr node = root while node : prev_node = next_node = None while node : # process for every level modify ( node . left ) modify ( node . right ) node = node . next node = next_node return root # use dummyHead.next to find each level's first node class Solution : def connect ( self , root : 'Node' ) -> 'Node' : dummyHead = Node ( 0 ) pre = dummyHead real_root = root while root : if root . left : # @note: here pre is same as dummyHead, pointing to 1st node of this level. this is before pre is updated to be other nodes pre . next = root . left pre = pre . next if root . right : pre . next = root . right pre = pre . next root = root . next if not root : # reach the end of current layer # shift pre back to the beginning, # get ready to point to the first element in next layer, # just like the same code before while loop pre = dummyHead # root comes down one level below to the first available non null node root = dummyHead . next # reset dummyhead back to default null, so that later it will point to next level's first node dummyHead . next = None return real_root ############### """ # Definition for a Node. class Node: def __init__(self, val=0, left=None, right=None, next=None): self.val = val self.left = left self.right = right self.next = next """ from collections import deque class Solution : # recursion, dfs def connect ( self , root : 'Node' ) -> 'Node' : if not root : return None # Initialize a queue with the root node and its level (0). queue = deque ([( root , 0 )]) # Process nodes level by level. while queue : current_node , level = queue . popleft () # If there's another node in the queue with the same level, # connect the current node's next pointer to the next node in the queue. if queue and queue [ 0 ][ 1 ] == level : current_node . next = queue [ 0 ][ 0 ] # Enqueue left and right children if they exist, along with their level. if current_node . left : queue . append (( current_node . left , level + 1 )) if current_node . right : queue . append (( current_node . right , level + 1 )) return root ############### # Definition for binary tree with next pointer. # class TreeLinkNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None # self.next = None class Solution : # @param root, a tree link node # @return nothing def connect ( self , root ): p = root pre = None head = None while p : if p . left : if pre : pre . next = p . left pre = p . left if p . right : if pre : pre . next = p . right pre = p . right if not head : head = p . left or p . right if p . next : p = p . next else : p = head head = None pre = NoneVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.