## Introduction

**Problem Statement : **Given a regular binary tree with left, right and peer node pointers. The left and the right pointers are already populated. We need to make the peer pointer point to the next right neighbor on the same level.

## Understanding the problem

Here is a diagram to explain what is needed. The red peer pointer points to the immediate right neighbor if the neighbor exists.

##### Approach 1

The first solution which comes in mind is to do a custom, level order traversal as done in the post. And, in each iteration of the inner loop, just link each of the node to the next in the queue.

This is a wonderful solution and always works without worrying much about the boundary conditions and any failures. But unfortunately it uses extra memory, i.e. the queue. The time complexity is still O(N) where N is the number of nodes as we are just visiting each node once.

**Can we do better?**

Well, not much can be done because we cannot save on running time. However, we can save some space, we might not need the auxiliary queue which we used in the first approach. We will follow a Recursive Approach.

##### Approach 2

Let us see what we can do when we visit a node P:

- If P has a left child P
_{L}then- If P has a right child P
_{R}then point P_{L}‘s peer pointer to the right child P_{R}. - Else, find the next neighbor of the P
_{L}and point P_{L}‘s peer pointer to the next neighbor.

- If P has a right child P
- If P has right child P
_{R}then- Find the next neighbor of the P
_{R}and point P_{R}‘s the peer pointer to the next neighbor.

- Find the next neighbor of the P

The steps to find the next neighbor is very simple and mentioned below:

**Next Neighbor :** It is the first child of P’s peer chain. A peer chain is the chain of all the nodes to the right which are connected horizontally on one level of a tree.

## Source Code for Binary Tree Linking Neighbors

Here is the source code, I am not writing the pseudo code for this as it is too simple. Let us directly jump to the source code. You can download the complete code from github repository.

##### Approach 1 – Iterative

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
private void addPeerApproachOne(Node root) { if (root == null) return; Queue Q = new ArrayDeque(); Q.add(root); while (!Q.isEmpty()) { int size = Q.size(); Node node = Q.remove(); if (node.left != null) Q.add(node.left); if (node.right != null) Q.add(node.right); for (int i = 1; i < size; i++) { Node nextNode = Q.remove(); node.peer = nextNode; node = nextNode; if (node.left != null) Q.add(node.left); if (node.right != null) Q.add(node.right); } } } |

##### Approach 2 – Recursive

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
private void addPeerApproachTwo(Node root) { if (root == null) return; if (root != null) { Node neighbor = null; if (root.left != null) { if (root.right != null) root.left.peer = root.right; else { neighbor = getNeighbor(root); root.left.peer = neighbor; } } if (root.right != null) { neighbor = getNeighbor(root); root.right.peer = neighbor; } } addPeerApproachTwo(root.left); addPeerApproachTwo(root.right); } private Node getNeighbor(Node node) { while (node.peer != null) { if (node.peer.left != null) { return node.peer.left; } else if (node.peer.right != null) { return node.peer.right; } node = node.peer; } return null; } |

## Conclusion

The fist approach gets tougher if we change the direction of linking where as the second approach is equally simple for both the directions. You can always try the reverse direction, which might be a different variant of the program.

The second method is space effective compared to the first one.

Don’t forget to **subscribe to TechieMe** to get updates on latest posts.