Data Structures – Is a Tree with Nodes Referencing Parent Still a Tree?

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.

You seem to have answered you own question. Have each node hold the count of its descendents plus one (itself). Every time you remove a node you decrement each count on the path back to the root. When inserting you instead increment each count on that path. This way each node contains the total number of nodes in its sub-tree. This will work fine for n-ary trees.

You can even perform the increment/decrement on the way down the tree if you are sure that the node you are inserting/deleting doesn't/does exist.

EDIT: Removing a node in the middle of the tree. Say you have a tree (labeled with the counts):

     |
    A(a)
   /   \
 B(b)  C(c)

Let's say you delete A and the rules say B should move up to fill it's place. As we said before you would decrement the counts on the path to the root, but you also need to update B's count as it is the new root of the subtree. You have to add C's count to B's:

     |
   B(b+c)
  /     \
...    C(c)