Binary Tree Linking Neighbors

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.
Binary Tree Linking Neighbors

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 PL then
    1. If P has a right child PR then point PL‘s peer pointer to the right child PR.
    2. Else, find the next neighbor of the PL and point PL‘s peer pointer to the next neighbor.
  • If P has right child PR then
    1. Find the next neighbor of the PR and point PR‘s the peer pointer to the next neighbor.

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

Approach 2 – Recursive

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.