CODEWITHSUNDEEP
algorithmdata-structurestreecomplexity-theory
Roman
Roman

Reputation: 66156

How to renew a tree from a list of its nodes faster then for O(n^2)?

Given: list of N nodes. Each node consists of 2 numbers: nodeID and parentID. parentID may be null (if it's a root node).

Is there an algorithm for recreating a tree from this list of nodes with time complexity better than O(N^2)?

Each node may have 0 or more children.

Short description of an algorithm with O(N^2) complexity: 

  find a root Node, put it to a Queue
  while Queue is not empty
      parentNode = Queue.pop()
      loop through nodes
          if currentNode.parentId = parentNode.id
              parentNode.addChild(currentNode)
              queue.push(currentNode)
              nodes.remove(currentNode)

It seems that this algorithm has O(N^2) time complexity (with small coefficient, maybe 0.25). But I may be wrong at complexity calculation here.

Upvotes: 3

Views: 177

Answers (3)

Svante
Svante

Reputation: 51501

I do not know what your input is, but let's assume that it is some sort of unordered list.

You can then create a tree structure by just putting them into a data structure that allows looking them up by their nodeID. For example, an array would do that. You then have a tree that is only linked in the direction of the parents. Transformation from an unordered list into this array is possible in linear time, assuming that the nodeIDs are unique.

In order to get the tree also linked in the direction of the children, you can prepare the nodes with a data structure (e.g. a list) to hold the children, and then do a second pass that adds each node to its parent's children list. This is also possible in linear time.

Upvotes: 1

ElKamina
ElKamina

Reputation: 7807

For each node initialize a list of children and for each node update the parent's children list with itself. Complexity O(n).

For node in NodeList:
    node.childList = []

For node in NodeList:
    if node.parent is not NULL:
        node.parent.childList.append(&node)

If the parent link is not readily available, then create a hash map. FWIW, the best worst case complexity of hash mapping is O(logn) for each insertion or lookup. So the final complexity becomes O(nlogn).

Upvotes: 1

Kaganar
Kaganar

Reputation: 6570

Since you've already got an external structure to the tree (a queue), I'm going to assume you don't mind using a bit of extra memory to get the job done faster.

Do it in two conceptual steps with a hash table:

  1. First make a hash table that relates node IDs to their actual node.
  2. Then look up a node's parent based on its parent's ID in the hash table and add the child to that parent.

More programatically:

for each node
    add node to hash table indexed by node's parent
for each node
    if parent is null set node as the root
    otherwise look up in the hash table the parent from the parent ID of the node
    add the node as a child of the found parent

The only potential issue with this technique is you don't necessarily end up with a valid tree until the very end. (That is, the root node may not have a child until the last link.) Depending on what you're doing with your tree, this may be an issue.

If that is an issue you can end up doing the same operation with a data structure that doesn't have that issue (just a vanilla tree with no attached data) and then mirror the structure.

All in all, this should be O(N) on the average.

Upvotes: 2

Related Questions