1
$\begingroup$

A rooted tree is a tree with a distinguished root node. When a rooted tree is embedded in a plane, a cyclic ordering is induced on the subtrees of the root. Such trees are called rooted plane trees.

Given a tree $T$, is there an algorithm that can output a rooted plane tree $T_r$ isormorphic to $T$ such that every node $v$ except the root is labelled with a number $f(v)$ so that $v$ is the $f(v)$-th child of its pararent?

What's the complexity?

$\endgroup$
1
  • 2
    $\begingroup$ DFS, linear time. $\endgroup$ Dec 9, 2021 at 16:38

1 Answer 1

1
$\begingroup$

Easy answer: Denote the root by $(0)$. Denote its $a\geq 0$ children by $(0,1),(0,2),\ldots,(0,a)$. Denote recursively the $b$ children of a vertex $(0,a_1,\ldots,a_{k-1})$ at height $k-1$ by $(0,a_1,\ldots,a_{k-1},1),(0,a_1,\ldots,a_{k-1},2),\ldots,(0,a_1,\ldots,a_{k-1},b)$.

Draw the vertex $(0,a_1,\ldots,a_{k-1},a_k)$ at the point $(a_k,k)$ of $\mathbb N^2$ and join it to its ancestor at $(a_{k-1},k-1)$ by an edge.

The answer to your question is then the function $(0,\ldots,a_k)\longmapsto a_k$.

The tree constructed above yields a tree which is immerged in the plane but not embedded (there is an overlay of all first descendants of vertices of given height). If you want to embed the tree, you have to replace the first coordinate $a_k$ of $(a_k,k)$ by the number of vertices $(0,b_1,\ldots,b_k)$ which are lexicographically smaller than $(0,\ldots,a_k)$.

$\endgroup$

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.