# [leetcode] Populating Next Right Pointers in Each Node

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

7.31.2015 updated

o(1) space complexity algorithm.

reference: http://www.cnblogs.com/felixfang/p/3647898.html

```// Space complexity: o(1)
// Make use of the 'next' pointer to implement a level order traversal algorithm.
//
// When we visit a node p, if it's not a leaf node, set p->left->next = p->right which links its two children.
// Besides, we maintain a preChild pointer to store the pre-visited right child, link it to the left child of next node in the upper level.
//
/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
**/
class Solution {
public:
while(root != NULL){
preChild = NULL;
//finish, leaf node
if(root->left == NULL){
break;
}
p = root;
while(p != NULL){
p->left->next = p->right;
if(preChild != NULL){
preChild->next = p->left;
}
preChild = p->right;
p = p->next;
}
root = root->left;
}
}
};```

```//Space Complexity: o(log(n)).
//This algorithm uses path[] array to store current visit path in the tree, which is equivalent to level order traversal.
//It compresses space complexity comparing to the traditional 'queue' algorithm.
//To be improved.
//o(1) is required.
/**
* Definition for binary tree with next pointer.
*  int val;
*  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
bool isNewLevel;
int path[100]; // Maximum 100 levels, if path[0] == 0, carry one to next digit. 0 means left child, 1 means right child.
int depth = 0; //current depth
for(int i = 0; i < 100; i++){
path[i] = -1;
}
p = next(root, path, depth, isNewLevel);
while(p != NULL){
if(pre == NULL || isNewLevel == true){
pre = p;
}
else{
pre->next = p;
pre = p;
}
p = next(root, path, depth, isNewLevel);
}
}
isNewLevel = false;
if(root == NULL){
return NULL;
}
//base condition
if(depth == 0){
depth = 1;
path[1] = 0;
isNewLevel = true;
return root->left;
}
path[depth]++;
int i = depth;
while(path[i] == 2){
path[i - 1]++;
path[i] = 0;
i--;
}
//carry digit
if(path[0] == 0){
path[0] = -1;
depth++;
path[depth] = 0;
isNewLevel = true;
}
for(int i = 1; i <= depth; i++){
p = path[i] == 0?p->left:p->right;
}
return p;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.