Count number of nodes in a level in a nested set

views:

233

answers:

+1 Q:

Count number of nodes in a level in a nested set

I am using Ruby (Ruby on Rails) and have a nested set of about 2000 nodes. Each node can only have two children.

What is the best way to determine how many nodes are in each level? Do I have to crawl the entire tree looking for sibling to do this?

Thanks!

+1 A:

In ActiveRecord there is an attribute called counter_cache, it's done specifically for such cases. Check Counter Cache Column screencast by Ryan Bates.

khelll 2009-10-13 05:54:27

Still got to populate the counter cache some how. And for that he's either got to wipe the data or traverse the entire tree. But once it's done, it never has to be done again.

EmFi 2009-10-13 06:30:50

True, one time traverse.

khelll 2009-10-13 07:02:58

I actually figured out a "quick" way to do this. Using the segment from "Depth of a Sub-Tree" on this page (link text) I am polling for depth using the given SQL with find_by_sql. I then iterate over the returned model results and count how many times each depth value occurs. Works great! Thanks all for looking and for your help!

Tricon 2009-10-13 07:14:15

ansaurus

tags:

views:

answers:

Count number of nodes in a level in a nested set

related questions