5

I'd like to construct a binary tree from a quite unusual input. The input contains:

  1. Total number of nodes.

  2. The integer label of the root.

  3. A list of all edges (vertices/nodes that are connected to each other). The edges in the list are UNSORTED, there is only one rule for determining left/right children - the child in the edge that appears first in list is always on the left. The order of child/parent in the vertices pair is also random.

I've come up with some straighforward solutions but they require multiple searches through the list of all edges (I'd basically find the 2 edges that have the labeled root in them and repeat this process for all the subtrees.)

I imagine this straightforward approach would be VERY inefficient for trees with a big amount of nodes, but I can't come up with anything else.

Any ideas for more efficient algorithms to solve this?

Here's an example for better visualization:

INPUT: 5 NODES, ROOT LABELED 2, LIST OF EDGES: [(1,0),(1,2),(2,3),(1,4)]

The tree would look like this:

        2
    1       3
 0     4

2 Answers 2

2

It is important to clarify whether the given edge list is stated to be directed or not.

If edges are given in a directed fashion (i.e. it is stated that any given edge A-B also includes the information that A is a parent of B) storing the edges in an adjacency list while recording number of incoming edges for each vertex in an array should be sufficient. Once you go through the array for the incoming edges, the vertex with 0 incoming edges(i.e. parents) should be the root. Then you can run a DFS in linear time complexity to traverse the graph and put it in any data structure that is best for your needs.

If the edges given are stated to be undirected, the scheme changes a bit. In that case, you don't have the concept of incoming and outgoing edge. In that case, as no structure for the array is specified(e.g. BST, etc.) you can basically consider any node with less than 3 edges as root and run DFS as mentioned above. (all the leaves and intermediary nodes with single child nodes)

1

A simple solution is: "Link all the edges in the tree that it!"

Start preparing a dictionary. If nodes don't exist by the start and end point, create them nodes. As it is random in nature, you can set their left and right pointers to NULL initially. You have rule - " the child in the edge that appears first in list is always on the left.". So create child accordingly. Also, you already know the root of the tree so you can iterate across the nodes you have constructed so far.

Through this you can generate tree in one shot.

Hope this helps!

1
  • Thank you very much for this solution, kind sir! This looks like exactly what I'm looking for! Could you clarify a few things, though? What exactly do I use the dictionary for? I assume the keys should be the respective nodes? If that's the case, should the values be the other node (that it is connected to) or something else?
    – P. Lance
    Mar 18, 2016 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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