4

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
  • 1
    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
  • 1
    Just edited a bit to elaborate more :) – qasimzee Sep 3 '15 at 2:21
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.

0

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]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.