Graph Theory37 sections · 1633 units
Open in Course

Example Tree

(Computing times step by step)

Tree: 11 (root) has children 22 and 33. Node 22 has child 44. DFS walk: Enter 11 (tin[1]=0, timer becomes 11), enter 22 (tin[2]=1, timer becomes 22), enter 44 (tin[4]=2, timer becomes 33), exit 44 (tout[4]=3), exit 22 (tout[2]=3), enter 33 (tin[3]=3, timer becomes 44), exit 33 (tout[3]=4), exit 11 (tout[1]=4).

Subtree of 22 covers [1,3)[1,3). Subtree of 11 covers [0,4)[0,4). Notice tintin values are unique while touttout values repeat (tout[4]=tout[2]=3).