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.

Jun

thats O(N^2) space in worst case scenario which is every node has one child (a noodle). – Gaza

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).

Cloison

what about the noodle scenario then? wouldent the preorder and postorder be exactly the same, so no node is an ancestor of another one? – Gaza

@WeaselFox: You mean like a linked list? Won't the traversals would be reverses of each other? – Cloison

Thanks. A notable property regarding post/pre-order numbers. – Jun

Answer 2

if you consider a tree where a node in the tree has n/2 children (say), the running time of setting the labels will be as high as O(n*n). So this labeling scheme wont work ....

Glennaglennie

Answer 3

There are linear time lowest common ancestor algorithms(at least off-line). For instance have a look here. You can also have a look at tarjan's offline LCA algorithm. Please note that these articles require that you know the pairs for which you will be performing the LCA in advance. I think there are also online linear time precomputation time algorithms but they are very complex. For instance there is a linear precomputation time algorithm for the range minimum query problem. As far as I remember this solution passed through the LCA problem twice . The problem with the algorithm is that it had such a large constant that it require enormous input to be actually faster then the O(n*log(n)) algorithm.

There is much simpler approach that requires O(n*log(n)) additional memory and again answers in constant time.

Hope this helps.

Noonan