Populating Next Right Pointers in Each Node - Solution & Explanation
Problem Statement
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, 212 - 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.
Approach Overview
Problem Overview: Given a perfect binary tree, connect every node's next pointer to its immediate neighbor on the same level. If there is no neighbor, the pointer should be NULL. The tree structure guarantees every parent has two children and all leaves are on the same level.
Approach 1: Level Order Traversal (Breadth-First Search) (Time: O(n), Space: O(n))
This approach processes the tree level by level using a queue. Push the root into the queue, then iterate through nodes level-wise. For each level, track the previous node and set its next pointer to the current node as you dequeue elements. After finishing a level, the last node naturally points to NULL. This method is straightforward and works for any binary tree, which makes it a good general template for problems involving level relationships. It directly uses Breadth-First Search on a Binary Tree.
Approach 2: Recursive Method (Time: O(n), Space: O(h))
The recursive strategy takes advantage of the perfect binary tree structure. For each node, connect node.left.next = node.right. Then connect across subtrees using node.right.next = node.next.left if the parent has a neighbor. Recursively apply the same logic to left and right children. The key insight: once a node's next pointer is set, it can be used to bridge connections across subtrees. This approach uses Depth-First Search and avoids an explicit queue.
Recommended for interviews: The BFS approach is the safest starting point because it works for both perfect and general binary trees. However, interviewers often expect the recursive solution for this specific problem since it leverages the perfect-tree constraint and reduces auxiliary space. Demonstrating BFS first shows correctness and clarity; transitioning to the recursive pointer-linking approach shows deeper understanding.
Approach 1: Level Order Traversal (Breadth-First Search)
This approach involves using a queue to perform a level order traversal of the tree. At each level of the tree, we'll connect the 'next' pointers of all nodes at that level. Since it is a perfect binary tree, each node at a level is directly followed by its sibling or by NULL if it is the last node at that level.
This C code uses a pointer 'current' to iterate levels starting from the root. Another pointer 'head' iterates nodes across a level, connecting left and right children. Each right child's next is connected to the next node's left child, if it exists.
Complexity
Time Complexity: O(N), where N is the number of nodes, since each node is processed once.
Space Complexity: O(1), as no extra space other than pointers is used—the perfect use of a constant space solution.
Approach 2: Recursive Method
The recursive method explores the tree depth-first and connects nodes level-wise. This approach effectively utilizes the call stack for traversal, aligning with the tree's inherent properties.
This C function uses recursion to traverse the tree, performing connections between each node's immediate left and right children, and recursively developing connections within each subtree.
Complexity
Time Complexity: O(N), which implies visiting each node once.
Space Complexity: O(logN) for recursion stack, since depth is proportional to the logarithm of node count.
Approach 3: BFS
Use a queue for level order traversal, and each time you traverse a level, connect the nodes of the current level in order.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Approach 4: DFS
Use recursion for preorder traversal, and each time you traverse to a node, connect its left and right child nodes in order.
Specifically, we design a function dfs(left, right), which points the next pointer of the left node to the right node. In the function, we first check whether left and right are null. If both are not null, point left.next to right, and then recursively call dfs(left.left, left.right), dfs(left.right, right.left), dfs(right.left, right.right).
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Level Order Traversal (Breadth-First Search) | Time Complexity: O(N), where N is the number of nodes, since each node is processed once. |
| Recursive Method | Time Complexity: O(N), which implies visiting each node once. |
| BFS | — |
| DFS | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal (BFS) | O(n) | O(n) | Best for clarity and works for any binary tree structure |
| Recursive Pointer Linking | O(n) | O(h) | Optimal for perfect binary trees where sibling relationships are guaranteed |
Video Solution
Populating Next Right Pointers in Each Node - Leetcode 116 - Python • NeetCode • 61,032 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Populating Next Right Pointers in Each Node easy or hard?
How to solve Populating Next Right Pointers in Each Node in O(n)?
Populating Next Right Pointers in Each Node Python or Java solution
What is the best approach for Populating Next Right Pointers in Each Node?
What data structure is used in Populating Next Right Pointers in Each Node?
What is the time complexity of Populating Next Right Pointers in Each Node?
Is Populating Next Right Pointers in Each Node asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Populating Next Right Pointers in Each Node with our built-in code editor and test cases.
Practice on FleetCode