Populating Next Right Pointers in Each Node

Med

#0116Time: O(N)Space: O(N)8 companies

Algorithms

Depth-First Search Breadth-First Search

Data structures

Linked List Tree Binary Tree

Companies

Flipkart Google Oracle ServiceNow

Prompt

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

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,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect 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, 2¹² - 1].
-1000 <= Node.val <= 1000

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

3 approaches with complexity analysis and trade-offs.

This approach uses a standard Breadth-First Search (BFS) or level order traversal. We traverse the tree level by level using a queue. For each level, we iterate through its nodes and connect each node to the one immediately following it in the queue, which corresponds to its right neighbor.

Algorithm

Handle the edge case where the root is null. If so, return null.
Initialize a Queue data structure and add the root node to it.
Loop as long as the queue is not empty. In each iteration, the queue holds all nodes of a single level.
Determine the number of nodes at the current level by getting the size() of the queue.
Iterate from i = 0 to size - 1. In each step: a. Dequeue a node, let's call it current. b. If this is not the last node of the level (i.e., i < size - 1), its next pointer should point to the next node in the level, which is currently at the front of the queue (queue.peek()). c. If the current node has a left child, enqueue it for the next level's processing. d. If the current node has a right child, enqueue it as well.
After the loops complete, all next pointers will be correctly populated. Return the root.

Walkthrough

The core idea is to process the tree one level at a time. We use a queue to store the nodes of the current level. Before processing a level, we record the number of nodes in it. Then, we dequeue nodes one by one. For each dequeued node, we set its next pointer to the node that is currently at the front of the queue, unless it's the last node of the level. While processing each node, we also enqueue its children for the next level. This ensures that we systematically connect all nodes at a given level before moving on to the next.

1/*2// Definition for a Node.3class Node {4    public int val;5    public Node left;6    public Node right;7    public Node next;8 9    public Node() {}10    11    public Node(int _val) {12        val = _val;13    }14 15    public Node(int _val, Node _left, Node _right, Node _next) {16        val = _val;17        left = _left;18        right = _right;19        next = _next;20    }21};22*/23 24class Solution {25    public Node connect(Node root) {26        if (root == null) {27            return null;28        }29 30        Queue<Node> queue = new LinkedList<>();31        queue.add(root);32 33        while (!queue.isEmpty()) {34            int levelSize = queue.size();35 36            for (int i = 0; i < levelSize; i++) {37                Node node = queue.poll();38 39                // If it's not the last node in the current level40                if (i < levelSize - 1) {41                    node.next = queue.peek();42                }43 44                // Add children for the next level45                if (node.left != null) {46                    queue.add(node.left);47                }48                if (node.right != null) {49                    queue.add(node.right);50                }51            }52        }53        return root;54    }55}

Complexity

Time

O(N)

Space

O(N)

Trade-offs

Pros

The logic is straightforward and easy to understand, as it's a direct application of level order traversal.
This approach is general and works for any binary tree, not just perfect ones (though the problem specifies a perfect binary tree).

Cons

This approach uses extra space for the queue. In the worst-case scenario (a complete, perfect binary tree), the maximum number of nodes at any level is (N+1)/2, where N is the total number of nodes. This leads to a space complexity of O(N), which does not satisfy the follow-up constraint of using only constant extra space.

A recursive approach can solve this problem by traversing the tree in a preorder fashion (Root, Left, Right). The function processes the current node by connecting its children, and then recursively calls itself for the left and right subtrees. The key is that connections at a level are made before descending to the next level.

Algorithm

Define a recursive function, say connect(root).
The base case for the recursion is when the root is null or it's a leaf node (root.left is null). In this case, simply return.
For the current root node, establish two types of connections: a. Connect the left child to the right child: root.left.next = root.right. b. If the root itself has a next pointer (meaning it's not the rightmost node of its level), connect its right child to the left child of its sibling: root.right.next = root.next.left.
Make two recursive calls. It's important to recurse on the left subtree first (connect(root.left)) and then the right subtree (connect(root.right)). This order ensures that the next pointers for a level are established from left to right, so when we process a node, its next pointer is already correctly set by its parent.

Walkthrough

The recursive solution relies on the fact that we can establish connections for the children of a node if we are at that node. A function connect(root) will perform the connections for the level below root.

First, we connect the direct children: root.left.next = root.right. This is straightforward.

Second, we need to connect nodes that do not share the same parent, for example, node 5 and node 6 in the example. This is done by connecting the right child of a node to the left child of its parent's next node. So, if root.next exists, we set root.right.next = root.next.left. This works because the next pointers for the current level are assumed to be already populated by the calls from the level above.

We must recurse on the left subtree before the right subtree. This ensures that when we are at connect(root.right), the root.next pointers have been fully established across the entire level.

1/*2// Definition for a Node.3class Node {4    public int val;5    public Node left;6    public Node right;7    public Node next;8 9    public Node() {}10    11    public Node(int _val) {12        val = _val;13    }14 15    public Node(int _val, Node _left, Node _right, Node _next) {16        val = _val;17        left = _left;18        right = _right;19        next = _next;20    }21};22*/23 24class Solution {25    public Node connect(Node root) {26        if (root == null) {27            return null;28        }29 30        // Connect the left child to the right child31        if (root.left != null) {32            root.left.next = root.right;33        }34 35        // Connect the right child to the next subtree's left child36        if (root.right != null && root.next != null) {37            root.right.next = root.next.left;38        }39 40        // Recurse for left and right subtrees41        connect(root.left);42        connect(root.right);43 44        return root;45    }46}

Complexity

Time

O(N)

Space

O(log N)

Trade-offs

Pros

The code is elegant and concise.
It meets the problem's follow-up constraints, as the implicit recursion stack space is not counted as extra space.
The logic naturally follows the tree's structure.

Cons

While the problem statement allows for the recursion stack space, in a general context, this approach uses O(log N) space for a balanced tree, which is not strictly O(1).
For extremely deep trees, this could lead to a stack overflow error, although this is unlikely given the problem constraints.

This is the most optimal approach, achieving constant extra space. It avoids recursion and explicit queues by using the next pointers that have already been established at the previous level. We iterate through the tree level by level, using a pointer to the start of each level and another pointer to traverse it.

Algorithm

If root is null, return null.
Initialize a pointer leftmost to the root. This pointer will always mark the beginning of the current level we are processing.
Start an outer loop that continues as long as leftmost has a left child (i.e., we are not at the last level).
Inside the outer loop, create a head pointer and initialize it to leftmost. This head pointer will traverse the current level from left to right.
Start an inner loop that continues as long as head is not null. a. Connect the children of the head node: head.left.next = head.right. b. Check if head has a next node. If it does, it means there's a node to its right on the same level. Connect head's right child to its neighbor's left child: head.right.next = head.next.left. c. Move the head pointer to the next node in the current level: head = head.next.
After the inner loop completes, all nodes in the level below leftmost are connected. Move to the start of that next level by updating leftmost = leftmost.left.
Once the outer loop finishes, return the root.

Walkthrough

This iterative solution cleverly uses the structure of the problem. We can think of it as a level-order traversal without a queue. We maintain a pointer, leftmost, which is the first node of each level. The outer loop iterates through the levels of the tree, starting from the root.

For each level (starting at leftmost), we use another pointer, head, to traverse from left to right using the next pointers that were set up by the previous iteration of the outer loop. As we traverse with head, we establish the next pointers for the level below.

There are two types of connections to make for each node head:

The connection between its own children: head.left.next = head.right.
The connection between its right child and the left child of its sibling: head.right.next = head.next.left. This is only possible if head.next is not null.

After traversing the entire level with head, we move down to the next level by setting leftmost = leftmost.left and repeat the process.

1/*2// Definition for a Node.3class Node {4    public int val;5    public Node left;6    public Node right;7    public Node next;8 9    public Node() {}10    11    public Node(int _val) {12        val = _val;13    }14 15    public Node(int _val, Node _left, Node _right, Node _next) {16        val = _val;17        left = _left;18        right = _right;19        next = _next;20    }21};22*/23 24class Solution {25    public Node connect(Node root) {26        if (root == null) {27            return null;28        }29 30        // Start with the root of the tree. This will be the leftmost node of the first level.31        Node leftmost = root;32 33        // Loop as long as we are not on the last level (i.e., leftmost has children).34        while (leftmost.left != null) {35            // 'head' will traverse the current level.36            Node head = leftmost;37 38            // Inner loop to traverse the nodes of the current level.39            while (head != null) {40                // Connection 1: Connect left child to right child.41                head.left.next = head.right;42 43                // Connection 2: Connect right child to the next node's left child.44                if (head.next != null) {45                    head.right.next = head.next.left;46                }47 48                // Move to the next node in the current level.49                head = head.next;50            }51            52            // Move to the start of the next level.53            leftmost = leftmost.left;54        }55 56        return root;57    }58}

Complexity

Time

O(N)

Space

O(1)

Trade-offs

Pros

Extremely efficient in terms of space, using only a few pointers, thus achieving O(1) space complexity.
Satisfies the follow-up constraint without any special assumptions about stack space.
Avoids the overhead of recursion and potential for stack overflow.

Cons

The logic can be slightly more complex to visualize and implement compared to the straightforward BFS approach.

Solutions

Solution

1/* // 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 root ; } Deque < Node > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { Node p = null ; for ( int n = q . size (); n > 0 ; -- n ) { Node node = q . poll (); if ( p != null ) { p . next = node ; } p = node ; if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } } return root ; } }

1/* // 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 ) { if ( ! root ) { return root ; } queue < Node *> q { { root } }; while ( ! q . empty ()) { Node * p = nullptr ; for ( int n = q . size (); n ; -- n ) { Node * node = q . front (); q . pop (); if ( p ) { p -> next = node ; } p = node ; if ( node -> left ) { q . push ( node -> left ); } if ( node -> right ) { q . push ( node -> right ); } } } return root ; } };

1""" # 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 """ ''' >>> d = deque((5,1,9,2)) >>> d.popleft() 5 >>> d.popleft() 1 >>> >>> >>> d = deque([5,1,9,2]) >>> d.popleft() 5 >>> d.popleft() 1 ''' from collections import deque class Solution : def connect ( self , root : "Optional[Node]" ) -> "Optional[Node]" : if root is None : return root # q = deque(root) ===> TypeError: 'Node' object is not iterable # make it a list [], so it's iterable q = deque ([ root ]) while q : prev = None for _ in range ( len ( q )): node = q . popleft () if prev : p . next = node prev = node if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) return root class Solution : def connect ( self , root : 'Node' ) -> 'Node' : if not root : return root l = [ root ] # list while l : size = len ( l ) for i in range ( size ): node = l . pop ( 0 ) # pop() is last, pop(0) is first of list if i < size - 1 : node . next = l [ 0 ] if node . left : l . append ( node . left ) if node . right : l . append ( node . right ) return root # recursion class Solution : def connect ( self , root : "Optional[Node]" ) -> "Optional[Node]" : self . _connect ( root , None ) return root def _connect ( self , current : 'Optional[Node]' , next_node : 'Optional[Node]' ) -> None : if current is None : return else : current . next = next_node # connect self . _connect ( current . left , current . right ) if next_node is not None : self . _connect ( current . right , next_node . left ) else : self . _connect ( current . right , None )

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

← Previous

Previous problem

Next problem

Solution

1/* // 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 root ; } Deque < Node > q = new ArrayDeque <>(); q . offer ( root ); while (! q . isEmpty ()) { Node p = null ; for ( int n = q . size (); n > 0 ; -- n ) { Node node = q . poll (); if ( p != null ) { p . next = node ; } p = node ; if ( node . left != null ) { q . offer ( node . left ); } if ( node . right != null ) { q . offer ( node . right ); } } } return root ; } }

1/* // 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 ) { if ( ! root ) { return root ; } queue < Node *> q { { root } }; while ( ! q . empty ()) { Node * p = nullptr ; for ( int n = q . size (); n ; -- n ) { Node * node = q . front (); q . pop (); if ( p ) { p -> next = node ; } p = node ; if ( node -> left ) { q . push ( node -> left ); } if ( node -> right ) { q . push ( node -> right ); } } } return root ; } };

1""" # 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 """ ''' >>> d = deque((5,1,9,2)) >>> d.popleft() 5 >>> d.popleft() 1 >>> >>> >>> d = deque([5,1,9,2]) >>> d.popleft() 5 >>> d.popleft() 1 ''' from collections import deque class Solution : def connect ( self , root : "Optional[Node]" ) -> "Optional[Node]" : if root is None : return root # q = deque(root) ===> TypeError: 'Node' object is not iterable # make it a list [], so it's iterable q = deque ([ root ]) while q : prev = None for _ in range ( len ( q )): node = q . popleft () if prev : p . next = node prev = node if node . left : q . append ( node . left ) if node . right : q . append ( node . right ) return root class Solution : def connect ( self , root : 'Node' ) -> 'Node' : if not root : return root l = [ root ] # list while l : size = len ( l ) for i in range ( size ): node = l . pop ( 0 ) # pop() is last, pop(0) is first of list if i < size - 1 : node . next = l [ 0 ] if node . left : l . append ( node . left ) if node . right : l . append ( node . right ) return root # recursion class Solution : def connect ( self , root : "Optional[Node]" ) -> "Optional[Node]" : self . _connect ( root , None ) return root def _connect ( self , current : 'Optional[Node]' , next_node : 'Optional[Node]' ) -> None : if current is None : return else : current . next = next_node # connect self . _connect ( current . left , current . right ) if next_node is not None : self . _connect ( current . right , next_node . left ) else : self . _connect ( current . right , None )

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.