# 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)