World's most popular travel blog for travel bloggers.

Assigning all nodes in a tree a parent and children

, , No Comments
Problem Detail: 

If one was given a tree in the form of a list of $A,B$ (not implying which one is the parent) pairs implying that node $A$ and $B$ were connected by an edge, how could a root node be determined and each node be assigned children and a parent such that by recursing up through its parent, its parents parent and so on the eventually one will eventually hit the root e.g.

Example Tree

Could be represented as 4,1 4,2 4,3 4,5 6,5

and a possible solution could be

1: parent:4, children: None 2: parent:4, children: None 3: parent:4, children: None 4: parent:None, children:1,2,3,5 5: parent:4, children: 6 6: parent:5, children: None

where 4 is the root.

Asked By : Marcus Handley
Answered By : David Richerby

The tree in your diagram is undirected. Undirected trees don't have a uniquely determined root because the edge $xy$ just means that nodes $x$ and $y$ are related: it doesn't specify that one is the parent of the other.

If you're told to make a particular node the root, you can do so by directing all of the edges away from the root, which you can do by depth-first search (or breadth-first search, or any other enumeration procedure).

Conversely, if the edges are directed, so $xy$ means "$x$ is the parent of $y$" (or vice-versa, if you want to adopt the opposite convention), then you can find the root by starting at any node and navigating to the parent until you find a node without a parent. Since the root is the unique node without a parent, you're done. You might also want to check that the graph really is a tree, i.e., that it is connected and acyclic.

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback