Graph Theory37 sections · 1633 units
Open in Course

Ancestor Check

(Fast relationship test)

Node uu is an ancestor of vv if DFS entered uu before vv and exited uu after vv. Condition: tin[u] <= tin[v] and tout[v] <= tout[u]. Check both inequalities in O(1)O(1) time. This is faster than LCA for simple ancestor queries. No extra data structures needed, tintin and touttout arrays.

This property makes it easy to check relationships between nodes without walking the tree. This check runs in O(1)O(1) time. No tree traversal needed. Compare two pairs of numbers and you get the answer.

Space complexity is O(n)O(n) for the data structures used.