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.
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$.
Here's what it might look like:
To tabulate the bounds requires a constant amount of time per node, and the complete table requires a constant amount of space per node. To check whether one node is a descendant of another requires constant time.