# Populate each next pointer to point to its next right node

Problem: Given a binary tree 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.
You may assume that it is a perfect binary tree (i.e. 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

Solution:

Implementation (Recursive approach):

```public void connectTree(TreeNode root) {
if(root==null){
return;
}
if(root.left!=null){
root.left.next = root.right;
}
if(root.right!=null){
if(root.next!=null){
root.right.next = root.next.left;
}
else{
root.right.next = null;
}
}

connectTree(root.left);
connectTree(root.right);
}
```

Non-Recursive approach:
Recursive solution isn’t constant memory, but O(log(n)) memory. To solve this, you just replace the recursive call with a while loop placing all of your logic.

```public void connectTree(TreeNode root)
{
while(root != null)
{
TreeNode ptr = root;
while(ptr != null)
{
if(ptr.left != null)
ptr.left.next = ptr.right;
if(ptr.right != null && ptr.next != null)
ptr.right.next = ptr.next.left;
ptr = ptr.next;
}
root = root.left;
}
}
```

Time Complexity: O(N), Where N is number of nodes in a tree.

Please write/comment if you find anything incorrect.

### One Thought on “Populate each next pointer to point to its next right node”

1. void updatingNextPointers(node *root) {
deque q;
int nodect = 0;

q.push_back(root);
while (!q.empty()) {
nodect = q.size();
while (nodect > 0) {
node *k = q.front();
q.pop_front();
nodect–;
if (nodect > 0)
k->next = q.front();
if (k->left)
q.push_back(k->left);
if (k->right)
q.push_back(k->right);
}
}
}

void printNextPointers(node *root) {
if (!root)
return;
cout<val<next);
printNextPointers(root->left);
printNextPointers(root->right);
}

Complexity: O(N)