1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Does your list of $(A,B)$ pairs require that $A$ represents the parent and $B$ the child? If not then any node of your example could take the role of root. If the answer is yes then you should search for the node that is not the second element of any $(A,B)$ pair and is the first element of (at least) one $(A,B)$ pair. $\endgroup$ – Sorrop Nov 6 '16 at 15:19
  • $\begingroup$ Every node can be a root. I don't get what the question here is. $\endgroup$ – Raphael Nov 7 '16 at 13:46
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not every directed tree has a root. $\endgroup$ – Raphael Nov 7 '16 at 13:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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