Tree traversal without recursive / stack usage (C#) ?

Question

Hi folks. I'm working with WPF and I'm developing a complex usercontrol, which is composed of a tree with rich functionality etc. For this purpose I used a View-Model design pattern, because some operations couldn't be achieved directly in WPF. So I take the IHierarchyItem (which is a node and pass it to this constructor to create a tree structure)

private IHierarchyItemViewModel(IHierarchyItem hierarchyItem, IHierarchyItemViewModel parent)
        {
            this.hierarchyItem = hierarchyItem;
            this.parent = parent;    

            List<IHierarchyItemViewModel> l = new List<IHierarchyItemViewModel>();
            foreach (IHierarchyItem item in hierarchyItem.Children)
            {
                l.Add(new IHierarchyItemViewModel(item, this));
            }
            children = new ReadOnlyCollection<IHierarchyItemViewModel>(l);
        }

The problem is that this constructor takes about 3 seconds !! for 200 items on my dual-core. Am I doing anythig wrong or recursive constructor call is that slow? Thank you very much!

Answer 1

There should be nothing wrong with a recursive implementation of a tree, especially for such a small number of items. A recursive implementation is sometimes less space efficient, and slightly less time efficient, but the code clarity often makes up for it.

It would be useful for you to perform some simple profiling on your constructor. Using one of the suggestions from: http://en.csharp-online.net/Measure_execution_time you could indicate for yourself how long each piece is taking.

There is a possibility that one piece in particular is taking a long time. In any case, that might help you narrow down where you are really spending the time.

Answer 2

Do you really need to build the whole tree? Can it be cached? Can you do lazy loading?

Answer 3

Well it seems that this recursion fits good for simple objects, but for very complex objects representing a tree node is it not an advantage.

Answer 4

OK I found a non recursive version by myself, although it uses the Stack. It traverses the whole tree:

Stack<MyItem> stack = new Stack<MyItem>();

stack.Push(root);

while (stack.Count > 0)
{
    MyItem taken = stack.Pop();

    foreach (MyItem child in taken.Children)                
       stack.Push(MyItem);                    

}