# LeetCode Populating Next Right Pointers in Each Node I and II: BFS with O(1) Space

## Overview

LeetCode Populating Next Right Pointers in Each Node I and II: use the linked list to simulate the role of a queue in BFS with O(1) Space cost.

## LeetCode Populating Next Right Pointers in Each Node I and II

(1) Given a binary tree

```struct TreeLinkNode {
}```

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

Note:

• You may only use constant extra space.
• You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

```1
/  \
2    3
/ \  / \
4  5  6  7```

After calling your function, the tree should look like:

```1 -> NULL
/  \
2 -> 3 -> NULL
/ \  / \
4->5->6->7 -> NULL```

(2) Follow up for problem “Populating Next Right Pointers in Each Node II“.

What if the given tree could be any binary tree? Would your previous solution still work?

## Solution: BFS with O(1) Space

The first problem is not hard because of the very special structure of the perfect tree. I did not go through the “I” problem but just directly head into the second follow up problem since it is more general, once we solve “II”, then “I” is obviously solved too. (BTW, it is also worth thinking about the solution specific to a perfect tree just for practice purpose).

If we are allowed to use additional memory, then we could just maintain two queues and do level-order traversal over the tree (i.e. level by level, each queue store all the nodes in a single level in turn). The idea is still do level order traversal but WITHOUT the additional queue (we are required to use constant memory). Think about how before you continue (hint: pay special attention to the structure of the tree node to see what does it have)

The following code implements this idea and is accepted by both LeetCode Populating Next Right Pointers in Each Node I and II:

```class Solution {

public:

if (NULL == root)
return ;

root->next = NULL;

while (curr) {

while (curr) {
if (curr->left) {
if (ptr) {
ptr->next = curr->left;
ptr = curr->left;
}
else {
ptr = next = curr->left;
}
ptr->next = NULL;
}
if (curr->right) {
if (ptr) {
ptr->next = curr->right;
ptr = curr->right;
}
else {
ptr = next = curr->right;
}
ptr->next = NULL;
}
curr = curr->next;
}
curr = next;
next = ptr = NULL;
}
}
};
```

And for the Populating Next Right Pointers in Each Node I, to further utilize the perfect tree property, we can simplify the code because we know the head of the next level, the following code could be accepted by Populating Next Right Pointers in Each Node I but not for II:

```void connect(TreeLinkNode *root) {
if (NULL == root)
return;
curr->next = NULL;

while (curr) {
next = curr->left;
while (curr) {
if (curr->left) {
curr->left->next = curr->right;
if (curr->next)
curr->right->next = curr->next->left;
else
curr->right = NULL;
}
curr = curr->next;
}
curr = next;
}
}
```

Also note although the problems are tagged with DFS from LeetCode, I really do not see any point of DFS because of the constant memory requirement.

## Summary

LeetCode Populating Next Right Pointers in Each Node I and II: use the linked list to simulate the role of a queue in BFS with O(1) Space cost.

Written on May 22, 2013