Cheap and Secure Web Hosting Provider : See Now

# Assigning all nodes in a tree a parent and children

, ,
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.

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.

###### 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.