# How to find the closest right neighbour in a tree?

Given a class:

``````public class Node
{
public List nodes[];
public Node right;   //NULL for now
}
``````

What's the best way to fill the "right" element of all tree nodes?

``````                        N
|
|
/ | \
/   |   \
C1--->C2-->C3
/ \         \
/   \         \
C11->C12 -----> C31
``````
• `node.right`? You are likely asking something harder than that - could you explain a bit more? – user40980 Sep 3 '15 at 0:32
• I think the question should be: "How to refresh node.right from the relevant existing nodes when inserting/deleting a node in this tree structure"? – Mandrill Sep 3 '15 at 2:16
• Just edited a bit to elaborate more :) – qasimzee Sep 3 '15 at 2:21

You can do normal BFS where at each level you determine the right of each node, something like this pseudocode.

``````while(queue of nodes is not empty) {
get size of queue into curLevelNodes
while(curLevelNodes is not zero) {
get current node into curNode
if there is a next node in the same level get it into nxtNode
curNode->right = nxtNode

don't forget to push the children of curNode to the queue

remove curNode from the queue

decrement curLevelNodes by one
}
}
``````

I would say make the variable `right` as a pointer.

The only problem here is that there is no guarantee of which node will right of which node, it will only follow the order of insertion.

One way to structure this is to use a multi dimensional array. By doing this, one dimension can represent columns, and the other rows. So, array location [11,127] would point to the node at column 11, row 127. This also makes visualising the structure in a 2D space very easy.

To find the node to the right of another, just increment the target nodes' column dimension, e.g:

``````var rightNeighbour = nodes[thisNode.Column +1, thisNode.Row]
``````