Skip to main content

Populating Next Right Pointers in Each Node

Problem Description​

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

Examples​

Example 1:

LeetCode Problem - Binary Tree

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]

Example 2:

Input: root = []
Output: []

Constraints​

  • The number of nodes in the tree is in the range [0, 212 - 1].
  • −1000<=Node.val<=1000-1000 <= Node.val <= 1000

Solution for Binary Tree Problem​

Intuition And Approach​

To populate each next pointer to point to its next right node in a perfect binary tree, we can perform a level order traversal and connect nodes at the same level.

Code in Different Languages​

Written by @Vipullakum007
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 curr = queue.poll();
if (prev != null) {
prev.next = curr;
}
if (curr.left != null) queue.offer(curr.left);
if (curr.right != null) queue.offer(curr.right);
prev = curr;
}
}
return root;
}
}

Complexity Analysis​

  • Time Complexity: O(n)O(n) where n is the number of nodes in the binary tree.
  • Space Complexity: O(m)O(m) where m is the maximum number of nodes at any level in the binary tree. In the worst case, the queue can contain all nodes at the last level, which is at most 2h−12^{h-1} where h is the height of the tree.