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.