Check if 2 tree nodes are related (ancestor/descendant) in O(1) with pre-processing

Question

Check if 2 tree nodes are related (i.e. ancestor-descendant)

• solve it in O(1) time, with O(N) space (N = # of nodes)
• pre-processing is allowed

That's it. I'll be going to my solution (approach) below. Please stop if you want to think yourself first.

---

For a pre-processing I decided to do a pre-order (recursively go through the root first, then children) and give a label to each node.

Let me explain the labels in details. Each label will consist of comma-separated natural numbers like "1,2,1,4,5" - the length of this sequence equals to (the depth of the node + 1). E.g. the label of the root is "1", root's children will have labels "1,1", "1,2", "1,3" etc.. Next-level nodes will have labels like "1,1,1", "1,1,2", ..., "1,2,1", "1,2,2", ...

Assume that "the order number" of a node is the "1-based index of this node" in the children list of its parent.

Common rule: node's label consists of its parent label followed by comma and "the order number" of the node.

Thus, to answer if two nodes are related (i.e. ancestor-descendant) in O(1), I'll be checking if the label of one of them is "a prefix" of the other's label. Though I'm not sure if such labels can be considered to occupy O(N) space.

Any critics with fixes or an alternative approach is expected.

Answer 1

You can do it in O(n) preprocessing time, and O(n) space, with O(1) query time, if you store the preorder number and postorder number for each vertex and use this fact:

For two given nodes x and y of a tree T, x is an ancestor of y if and only if x occurs before y in the preorder traversal of T and after y in the post-order traversal.

(From this page: http://www.cs.arizona.edu/xiss/numbering.htm)

What you did in the worst case is Theta(d) where d is the depth of the higher node, and so is not O(1). Space is also not O(n).