Does anyone know of a quick algorithm for painting a tree with L and R values?

(Don’t worry - this isn’t a uni/college assignment or anything)

eg. For tree
A
B C
D E F G H
I J K

Each node (letter in this case) has two values - a left or L value and a right or R value.

I need an algorithm that paints the entire tree with L and R values such that any ancestor’s L and R values strictly bound all its descendants L and R values. (A sort of pre-stored transitive closure approach).

eg. A.L = 1 and A.R = 22
B.L = 2 and B.R = 9
C.L = 10 and C.R = 21
D.L = 3 and D.R = 4
E.L = 5 and E.R = 6
F.L = 7 and F.R = 8
…

Ruby, pseudo-code or C would be perfect!

Thanks in advance

Lachlan Pitts
Technical Consultant
SoftWorks Australia Pty Ltd

I need an algorithm that paints the entire tree with L and R
values such that any ancestor’s L and R values strictly bound
all its descendants L and R values. (A sort of pre-stored
transitive closure approach).

…and such that the [L,R] intervals of siblings are disjoint?

Otherwise you can take L = 0, R = 2*depth for the root and do L–, R++
for each level down…

“Lachlan Pitts” Lachlan_Pitts@softworks.com.au wrote in message
news:426B71FE520A87419C9C4E1BBD2F18F27269C6@swa02.softworks.lan.au…

I need an algorithm that paints the entire tree with L and R values such
that any ancestor’s L and R values strictly bound all its descendants L and
R values. (A sort of pre-stored transitive closure approach).