Graph Theory37 sections · 1633 units
Open in Course

Entry-Only Variant

(Just tin values)

Store only tin[v] for each node. This gives you a DFS preorder traversal numbering.

Use this when you need to check ancestor relationships quickly: uu is an ancestor of vv if tin[u] < tin[v] and uu is on the path from root to vv. You lose the ability to identify subtree ranges, so this variant is less useful for most problems.

However, combined with tout, you can check ancestry in O(1)O(1): uu is an ancestor of vv if tin[u] <= tin[v] and tout[v] <= tout[u].