Basically, this is being modeled in a modified pre-order tree traversal where the left and right numbers come from traversing the edges of the tree. The number of descendants for a given node would result from the calculation, (right - left - 1) / 2 ... so, (18 - 1 - 1) / 2 = 8 descendants from the root node.
I should have specified before, but this tree/table is actually in a 2-dimensional array format, so queries are not really usable. Either way, it would appear that the query you specified would calculate the total number of nodes in the tree (9), not the depth of the tree(4). What I am trying to find is the length of the longest branch of the tree, and short of writing a recursive function, I am not sure how else to calculate this. Thanks -- Jeff -----Original Message----- From: Barney Boisvert [mailto:[EMAIL PROTECTED] Sent: Sunday, July 10, 2005 4:38 PM To: CF-Talk Subject: Re: Depth of a tree? The left/right fields seem to be for nested sets, right? Something like this will work: SELECT MAX(c) FROM ( SELECT COUNT(t2.title) as c FROM fruit t1 INNER JOIN fruit t2 where t2.left <= t1.left and t2.right >= t1.right GROUP BY t1.id ) t On another note, there's no need to record the parent field in the table, it's computable from the left/right values, and is an instance of [potentially troublesome] denomalization. cheers, barneyb On 7/10/05, Jeff Chastain <[EMAIL PROTECTED]> wrote: > I have a hierarchical set of data stored in tree format. The tree may > or may not be a binary tree ... i.e. each node could have 0 thru N sub-nodes. > Now, I need to calculate the length of the longest branch, or > otherwise, the depth of the tree. My comp. sci. days are a long way > behind me, so does anybody know how this would be calculated? An > example tree I have been working with is as follows ... > > +--------+--------+------+-------+ > | parent | title | left | right | > +--------+--------+------+-------+ > | | Food | 1 | 18 | > | Food | Fruit | 2 | 11 | > | Fruit | Red | 3 | 6 | > | Red | Cherry | 4 | 5 | > | Fruit | Yellow | 7 | 10 | > | Yellow | Banana | 8 | 9 | > | Food | Meat | 12 | 17 | > | Meat | Beef | 13 | 14 | > | Meat | Pork | 15 | 16 | > +--------+--------+------+-------+ > > So, in this case, the depth would end up being 4 ... Food, Fruit, Red, > Cherry - or - Food, Fruit, Yellow, Banana. > > Any ideas? > > Thanks > -- Jeff > -- Barney Boisvert [EMAIL PROTECTED] 360.319.6145 http://www.barneyb.com/ Got Gmail? I have 50 invites. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~| Find out how CFTicket can increase your company's customer support efficiency by 100% http://www.houseoffusion.com/banners/view.cfm?bannerid=49 Message: http://www.houseoffusion.com/lists.cfm/link=i:4:211517 Archives: http://www.houseoffusion.com/cf_lists/threads.cfm/4 Subscription: http://www.houseoffusion.com/lists.cfm/link=s:4 Unsubscribe: http://www.houseoffusion.com/cf_lists/unsubscribe.cfm?user=11502.10531.4 Donations & Support: http://www.houseoffusion.com/tiny.cfm/54
