How to find the closest right neighbour in a tree?

Question

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

Answer 1

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.

Answer 2

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]