Introduction

Yes, you can answer "is node b a descendant of node a" in O(1) time, but only after preprocessing the tree. The standard technique is to run one depth-first traversal, assign each node an entry time and an exit time, and then use interval containment for every later query. Without that preprocessing, no general tree can support arbitrary descendant queries in constant time from raw pointers alone.

The Core Idea: Entry and Exit Times

During a depth-first search, record two numbers for each node:

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

The crucial property is:

• 'u is an ancestor of v if and only if tin[u] <= tin[v] and tout[v] <= tout[u]'

That works for binary trees, multiway trees, file-system trees, and any rooted tree where children are visited recursively.

Why the Interval Test Works

A DFS visits an entire subtree as one contiguous interval in traversal time. So when you enter node u, every descendant of u gets visited before you exit u.

That means each subtree becomes an interval:

• node u owns the interval from tin[u] to tout[u]
• every descendant of u lies fully inside that interval
• nodes outside the subtree fall outside that interval

Once those intervals exist, a descendant test is just two integer comparisons.

Python Example

Here is a complete runnable implementation for a multiway tree represented as an adjacency list:

1class DescendantIndex:
2    def __init__(self, tree, root):
3        self.tree = tree
4        self.tin = {}
5        self.tout = {}
6        self._time = 0
7        self._dfs(root)
8
9    def _dfs(self, node):
10        self.tin[node] = self._time
11        self._time += 1
12        for child in self.tree.get(node, []):
13            self._dfs(child)
14        self.tout[node] = self._time
15        self._time += 1
16
17    def is_descendant(self, ancestor, node):
18        return (
19            self.tin[ancestor] <= self.tin[node]
20            and self.tout[node] <= self.tout[ancestor]
21        )
22
23
24tree = {
25    "A": ["B", "C", "D"],
26    "B": ["E", "F"],
27    "C": [],
28    "D": ["G"],
29    "E": [],
30    "F": [],
31    "G": [],
32}
33
34index = DescendantIndex(tree, "A")
35print(index.is_descendant("A", "F"))
36print(index.is_descendant("B", "F"))
37print(index.is_descendant("C", "F"))

This prints True, True, and False.

Complexity

The preprocessing cost is O(n) because each node and edge is visited once during DFS. After that:

• each descendant query is O(1)
• extra storage is O(n) for the two timestamp arrays or maps

That tradeoff is excellent when you have many queries against a mostly static tree.

When This Is the Right Answer

This method is ideal when:

• the tree is built once and queried many times
• you care about ancestor-descendant checks only
• the structure changes rarely or can be reindexed cheaply

Typical examples include:

• access-control trees
• organization charts
• DOM or AST analysis
• category hierarchies

It is less attractive when the tree is changing constantly, because each structural update may require recomputing intervals for part or all of the tree.

What If the Tree Changes Often?

If you insert and move nodes frequently, the timestamp intervals can become stale. In that case, there are two main options:

• rebuild the timestamps after batches of updates
• use a more advanced dynamic-tree structure if the problem truly needs online updates

For most application code, rebuilding is simpler and more reliable unless the update frequency is extremely high.

Beware of Rooting and Identity

The algorithm assumes a rooted tree. In other words, "descendant" has meaning only after you choose the root and traversal direction.

You also need stable node identity. If the same node value can appear in multiple places, use unique IDs rather than human-readable labels alone.

For example, this is safer than using names directly:

1tree = {
2    1: [2, 3],
3    2: [4],
4    3: [],
5    4: [],
6}

The algorithm itself does not care whether IDs are integers or strings. It only cares that they uniquely identify nodes.

Common Pitfalls

The biggest mistake is claiming O(1) without mentioning the preprocessing step. The query is constant time only after the DFS index is built.

Another mistake is storing only an entry time and not an exit time. One timestamp is not enough to distinguish descendant relationships safely.

Developers also sometimes apply the method to graphs with cycles. It is a tree technique. If the structure is a general graph, the ancestor-descendant idea is no longer enough.

Finally, be careful with equality. Depending on your definition, a node may or may not count as a descendant of itself. The comparison above treats a node as being inside its own interval. If you want strict descendant only, add ancestor != node.

Summary

• A rooted multiway tree can support O(1) descendant checks after O(n) preprocessing.
• Use DFS entry and exit times to assign each subtree an interval.
• Node v is in the subtree of u when tin[u] <= tin[v] and tout[v] <= tout[u].
• The method is excellent for static or mostly static trees.
• It is not a free O(1) solution for constantly mutating trees or general graphs.