Introduction

Yes, you can answer ancestor and descendant queries in O(1) time after linear preprocessing. The standard method is to run a depth-first traversal once, record entry and exit times for every node, and then compare intervals.

The Preprocessing Idea

During DFS, give each node two timestamps:

• 'tin[node] when you first enter the node'
• 'tout[node] when you finish exploring its subtree'

These timestamps create a nesting property:

node u is an ancestor of node v if and only if:

• 'tin[u] <= tin[v]'
• 'tout[u] >= tout[v]'

That works because every node in a subtree is visited completely between the ancestor's entry and exit times.

Python Example

1tree = {
2    1: [2, 3],
3    2: [4, 5],
4    3: [6],
5    4: [],
6    5: [],
7    6: []
8}
9
10tin = {}
11tout = {}
12timer = 0
13
14
15def dfs(node):
16    global timer
17    tin[node] = timer
18    timer += 1
19
20    for child in tree[node]:
21        dfs(child)
22
23    tout[node] = timer
24    timer += 1
25
26
27def is_ancestor(u, v):
28    return tin[u] <= tin[v] and tout[u] >= tout[v]
29
30
31dfs(1)
32
33print(is_ancestor(2, 5))
34print(is_ancestor(3, 5))

Output:

True
False

The preprocessing takes O(n) time for a tree with n nodes, and each query afterward is constant time.

Why It Works

DFS enters a node before any node in its subtree and exits it after every node in its subtree is done. So each subtree becomes an interval, and subtrees are either nested or disjoint.

That turns ancestry into a simple interval-containment test.

This is much cleaner than walking parent pointers on every query, which would take up to O(h) time where h is the tree height.

Extending the Technique

The same timestamps are useful for more than ancestry checks. They often appear in:

• subtree queries
• Euler tour array techniques
• lowest common ancestor preprocessing
• flattening trees for segment trees or Fenwick trees

So even if you only need ancestor checks today, the preprocessing is a strong general-purpose foundation.

Handling Parent Pointers and Root Choice

You need a rooted tree for the ancestor relation to make sense. In an undirected tree, choose a root first and make sure DFS does not walk back to the parent as if it were a child.

If your input stores parent pointers already, preprocessing is still worth it when you need many queries. One-time DFS gives you O(1) queries instead of repeated upward walks.

For example, a single query might be cheap enough with parent pointers alone, but thousands or millions of ancestry checks make the timestamp method much more attractive. That is why this trick appears so often in competitive programming and tree-heavy systems code.

Common Pitfalls

• Forgetting to root the tree before talking about ancestors.
• Using only entry time without exit time.
• Reusing the technique on general graphs without preventing revisits.
• Assuming this handles dynamic tree edits automatically. If the tree changes, the timestamps may need recomputation.
• Mixing strict and non-strict comparisons inconsistently.

Summary

• Preprocess the tree once with DFS and record entry and exit times.
• Node u is an ancestor of node v when u's interval contains v's interval.
• Preprocessing is O(n) and each query is O(1).
• The method works on rooted trees and extends naturally to many other tree algorithms.
• For many ancestor queries, this is one of the simplest and most effective techniques available.