How to get a random item from the tree given a parent node?

Question

I have a scenario where I would like to randomize the display of some items. Given a Parent item, how can I randomly select one of its child items?

Of course I could load ALL the children and apply some random index or whatnot... but that would be wildly inefficient.

I'm wondering if this is also inefficient:

Parent.Children[random(Parent.Children.Count)]?

At what point do the items get loaded when you access Parent.Children?

Answer 1

Do you have the entire tree structure on hand? Then you could do some sort of random traversal. For example, you could select a random item from a binary tree like so (pseudo-code):

sub randomNode(node):
   randomVal = random(0, 3); // random value between 0 and 3

   if(randomVal == 0):
     return randomNode(node.left) if node.left != null else return node;
   elseif(randomVal == 1):
     return randomNode(node.right) if node.right != null else return node;
   else
     return node;

For an n-ary tree, you could have something like this:

sub randomNode(node):
   randomVal = random(0, 2)

   if(randomVal == 0):
     return randomNode(node.children[random(0, node.children.length)]) if node.children.length != 0 else return node;
   elseif(randomVal == 1):
     return node;

Doing parent.children[random(parent.children.count)] doesn't seem inefficient to me; it's what I've used in the algorithm above. As far as your last question, I guess it depends on how you've implemented your tree. If you've built up a tree structure on your own then you must have the whole tree structure on hand. If you're using a framework, then it depends on the implementation of that framework.

Answer 2

Item.Children is a lazy loaded property, and I would definitely not recommend using it exactly in the way you show here.

Before posting this, I did some digging through the API to see if there really isn't a way to get to the count of childitems without loading this property, but alas I couldn't really find any way that would seem "legitimate". Only the .HasChildren property seems to relate - and it seems to work by doing most (but not all) of what the .Children property does already.

However, given that it is lazy loaded, store the result of the property in a private field for maximum efficiency. I remember reading this in an official developer guideline at one point, I can dig out the exact reference if needed.

ChildList itemChildren = myItem.Parent.Children;
// Continue doing random() etc here, but using the itemChildren field.