From: Lachlan Pitts <Lachlan_Pitts@...>
Date: 2002-09-03T12:19:02+09:00
Subject: Efficient construction of a L/R minmax tree

Hi rubys,

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

email: 	mailto:Lachlan_Pitts@softworks.com.au
voice: 	+61 7 3511 7000