Property of the numbering in preorder traversal of the tree

Question

$v$ denotes the vertex which has been asigned the number $v$.

The vertices are numbered in the order visited.

In preorder all vertices in a subtree with root $r$ have numbers no less than $r$.

More precisely, if $D_r$ is the set of descendants of $r$, then $v$ is in $D_r$ if and only if $$r\leq v<r+||D_r||$$

Could you explain me the last inequality??

It stands that $r\leq v$ because the root is visited before its descendants, right??

But why does it stand that $v<r+||D_r||$ ??

Answer 1

You are right $r\leq v$ because you visit the root before its descendants.

The other inequality comes from the fact that you visit only the descendant of the root $r$ before visiting its descendant $v$.

Hence the number of vertices visited between $r$ and $v$ is bounded by $|D_r|-1$ (minus $1$ because $v$ is not visited yet).

I hope it's clear.

Answer 2

Yes, root is visited before its descendants and all descendants of $r$ are visited before visiting a node which is not in the subtree rooted at $r$. So, descendants of $r$ will be numbered $r+1, r+2,...,r+||D_{r}||.$ Hence $v$ is a descendant of $r$ if and only if

\begin{align} r<v \le r+||D_{r}|| \end{align}