1
$\begingroup$

(Diestel, Graph Theory) Corollary 1.5.2: Every tree has an enumeration of the vertices $\{v_1, v_2\ldots v_n\}$ such that each vertex $v_i$, with $i\geq 2$, has a unique neighbour in $\{v_1, v_2\ldots v_{i-1}\}$.

I am wondering if there is an efficient algorithm that could produce such an enumeration in $O(n)$.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

Pick an arbitrary root. Do a preorder traversal. Now, each vertex has a unique neighbour prior to it in the ordering, namely its parent.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Could you describe what you mean by pre-order traversal? AFAIK, pre-order traversals are only defined for binary trees while the theorem holds for any type of tree. $\endgroup$
    – Archimedesprinciple
    Dec 19, 2022 at 18:38
  • $\begingroup$ Preorder traversal is easily extended to non-binary trees by the straightforward generalisation: you visit the root first, then for each of the children, you recurse into the subtree rooted at that child. $\endgroup$
    – Pål GD
    Dec 19, 2022 at 18:44
  • $\begingroup$ The order in which you process the children doesn't matter. $\endgroup$
    – Pål GD
    Dec 19, 2022 at 18:45

Your Answer

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

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