Data Structures – Tree-Like Structure with Multiple Root Nodes

You could use a BFS algorithm (a graph algorithm explained on Wikipedia), starting from the node you want to make root.

The algorith behaves like this:

procedure BFS(G,v,btree):
      create a queue Q
      enqueue v onto Q
      mark v
      btree = new Tree(v);//Create a tree structure with v as root
      while Q is not empty:
          t ← Q.dequeue()
          btree.add(t) // Here its where you add elements to your tree
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q

When Q is empty means you processed all the possible nodes and all of them have been added to your binary tree (btree).

Once you have your btree you can apply any simple algorithm to obtain what you need

With the caveat that each node has exactly one parent except for the root node, calling this a tree is fine.

With respect to building the tree, one way is to do the following:

1. keep some kind of associative lookup of existing nodes indexed by their unique ID (I don't know PHP, but I'm thinking some kind of dictionary or hash)
2. keep a similar lookup of orphan nodes, indexed by parent ID
3. when you create a node:
   1. see if it's parent is in the existing set
      • if it is, attach the child to the parent
      • if not, insert the new node in the orphan set
   2. then see if any orphans are waiting for it (nodes in the orphan set indexed with the new node's ID)
      • if there are, attach them and remove them from the orphan set
   3. finally, add the new node to the existing set
4. at the end, anything still in the orphan set is either a problem, or should be attached to your root node.

Assuming, of course, you have some unique ID to identify parent/child relationships.

Oh, and I seem to have used the word set to mean some kind of associative container - note that it can't be unique or 3.2 will have problems with multiple orphans of the same node.