CODEWITHSUNDEEP
algorithmtreeedgesconstruct
mirt
mirt

Reputation: 1493

Build tree from edges

I have the edges and i want to build a tree with it.

The problem is that i can construct my tree structure only when edges are in specific order. Example of orders:

(vertex, parent_vertex)

good:              bad:
(0,  ) <-top       (3, 2)
(1, 0)             (1, 0)
(2, 1)             (3, 2)
(3, 2)             (0,  ) <-top

I iterate throw the edges and for current vertex trying to find it's parent in created tree, then i construct the node and insert it.

result tree:

0 - 1 - 2 - 3

So there is always must exist a parent in the tree for the new added vertex. The question is how to sort the input edges. Voices tells me about the topological sort, but it's for vertexes. Is it possible to sort it right?

Upvotes: 2

Views: 8435

Answers (1)

Dhandeep Jain
Dhandeep Jain

Reputation: 166

@mirt thanks for pointing out the optimizations on my approach, have you got any better? i will put the below algo for ref

initially construct a hash map to store elements that are there in tree : H, add the root (null in your case/ or anything that represent that root)

taking the pair (_child, _parent)

  1. loop through the whole list. in the list. (each pair is the element)
  2. for each pair, see if the _child and _parent is there in the hash map H, if you dont find, create the tree node for the missing ones and add them to H , and link them with the parent child relationship.
  3. you will be left with the tree at the end of iteration.

complexity is O(n).

Upvotes: 2

Related Questions