# A way to codify (pre-calculatate) if a one Tree Node is a descendant of another

I have a simple, 1-directional tree representing the veins in a human body. It looks somewhat like this (red dots are nodes, blood flow is always downwards, sorry for my drawing):

What I need is a way to compare any two node N1 & N2 to see if N2 is downstream of N1, i.e. blood reaching N2 has passed N1. Which is the same as testing if N2 is a descendant of N1, I think.

I could of course use a recursive solution but that's WAY too slow. And a lookup table is WAY to big on memory.

What I'm trying to figure out is if there is a way to number each node and save this information, so that at runtime I can do a simple comparison of the two nodes' values as a O(1) complexity operation. I initially thought of simply using the distance from the source but of course that's no good.

Is this even possible and if so how could I approach it? I should re-emphasise this is for run-time use, in fact it's for real-time rendering (say 30Hz) where each frame all nodes must be compared against an 'insertion node' to see if they are downstream... which means it has to be very time & space efficient.

-
What's your recursive solution that's "WAY too slow"? Just walk up the tree from $N_2$ until you hit either $N_1$ or the root. You can write this in a while loop. – Rahul Jan 23 '13 at 23:18
@rahul Much better solutions are available. – MJD Jan 24 '13 at 3:01
This is being done in a shader program on the GPU, which basically puts strict limits on the types of data structures and control structures (looping etc) I can do. I'm not sure I can explain better without a lot of words! – Mr. Boy Jan 24 '13 at 10:06

First, prepare a data structure as follows: Each node $N$ will be assigned a lower and an upper bound, $[lo, hi]$, where $lo$ is less than the smallest lower bound of any descendant, and $hi$ greater than the greatest upper bound of any descendant of $N$.
To prepare this data structure, traverse the tree in depth-first order. Maintain a counter, $c$. The first time your traversal reaches a new node $N$, set its lower bound $lo_N = c$ and increment $c$. The last time your traversal reaches $N$, just before the traversal ascends to $N$'s parent, set $N$'s upper bound $hi_N = c$ and increment $c$. For a leaf $\ell$, you have the option of setting $lo_\ell = hi_\ell$ or $lo_\ell + 1 = hi_\ell$; either way will work. Store all the $lo$ and $hi$ values in a table so that you can look up a node's $lo$ and $hi$ values efficiently.
Once you have the mapping from nodes to $[lo, hi]$ bounds, it is easy to efficiently check if $M$ is a descendant of $N$: Look up the bounds for $M$ and $N$, and then $M$ is a descendant of $N$ if and only if both $lo_M \ge lo_N$ and $hi_M\le hi_N$.
I see that I skipped the label 10 in my diagram, but it doesn't actually matter as long as the counter $c$ is strictly increasing. – MJD Jan 24 '13 at 3:03