Replacing recursive with loop

Question

I am working on an ASP.Net page, and there is tree view in it. In the tree view some nodes have nested nodes like branches. I have data in a list of custom objects in the following format:

Id, Description, parentId

Right now, I am using a function to recursively add nodes to the tree view. The following is code snippet:

private bool findParentAddNode(string id, string description, string parentid, ref List<CustomTreeNode> treeList)
{
    bool isFound = false;
    foreach (CustomTreeNode node in treeList)
    {
        if (node.id == parentid)//if current node is parent node, add in it as its child
        {
            node.addChild(id, description, parentid);
            isFound = true;
            break;
        }
        else if (node.listOfChildNodes != null)//have child nodes
        {
            isFound = findParentAddNode(id, description, parentid, ref node.listOfChildNodes);
            if (isFound)
                break;
        }

    }

    return isFound;
}

The above technique works well but, for more then 30K nodes, its performance is slow. Please suggest an algorithm to replace this recursive call with loops.

Are you sure the recursion is the problem? Unless your tree shape is odd that shouldn't be that many levels. — millimoose
– millimoose, Commented Feb 16, 2013 at 12:44
I believe for loops will be still slow with 30K nodes. Recursive approach is good if you don't call the function with the same parameters — ogzd
– ogzd, Commented Feb 16, 2013 at 12:44
@NadeemJamali Visual Studio should include a profiler. Also, you might want to look into an introductory AI / machine learning textbook, those cover tree search algorithms well. (They'd tell you that for a recursive tree search, iterative-deepening DFS tends to have nicer properties than BFS if you don't know how deep in the tree you should expect the result.) — millimoose
– millimoose, Commented Feb 16, 2013 at 12:59
see this post http://stackoverflow.com/q/308816/1174942. I've used JetBrains dotTrace before. It is wonderfull but not free. — Moha Dehghan
– Moha Dehghan, Commented Feb 16, 2013 at 13:01
It looks like your scanning through the whole existing tree for every node you insert. This will lead to a n^2 algorithm. I'd propose to add the nodes in two passes: first just create all nodes with id and description and put them in a map (hashtable). Then iterate over all nodes again, look up the correct parent in the map and append the node as a child. — raymi
– raymi, Commented Feb 16, 2013 at 14:46

Pete Kirkham · Accepted Answer · 2013-02-16 21:54:51Z

As it recurses down the tree, the code is doing a linear search over the lists of child nodes.

This means that for randomly distributed parent ids, after adding N nodes to the tree it will on average search N/2 nodes for the parent before adding the N+1th node. So the cost will be O(N²) on the number of nodes.

Instead of a linear scan, create an index of id to node and use that to find the parent quickly. When you create a node and add it to the tree, also add it to a Dictionary<int,CustomTreeNode>. When you want to add a node to parent, find the parent in the index and add it. If addChild returns the child it creates, then the code becomes:

Dictionary<int,CustomTreeNode> index = new Dictionary<int,CustomTreeNode>();

private bool findParentAddNode(string id, string description, string parentid)
{
    if ( !nodeIndex.TryGetValue ( parentid, out parentNode ) ) 
        return false;

    index[id] = parentNode.addChild(id, description, parentid);

    return true;
}

You will need to add the root of the tree to the index before using findParentAddNode.

millimoose · Accepted Answer · 2013-02-16 12:56:32Z

-1

An iterative version of a breadth-first search should be something like the following:

var rootNodes = new List<CustomTreeNode> { new CustomTreeNode() };

while (rootNodes.Count > 0) {
    var nextRoots = new List<CustomTreeNode>();
    foreach (var node in rootNodes) {
        // process node here
        nextRoots.AddRange(node.CustomTreeNode);
    }
    rootNodes = nextRoots;
}

That said, this isn't tested, and since it's a BFS, isn't optimal w/r/t memory. (Memory use is O(n), not O(log n) compared to DFS or iterative-deepening DFS.)

answered Feb 16, 2013 at 12:56

millimoose

40.1k11 gold badges90 silver badges138 bronze badges

2 Comments

Nadeem Jamali Over a year ago

It looks better, I'll test it. Thanks millimoose.

millimoose Over a year ago

@NadeemJamali You might also look at doing an iterative DFS instead of a BFS but that's a little uglier in C# since you need to modify a list instead of using foreach. (And might or might not need to use a LinkedList because of the array-based List because of the frequent prepends.) A further microoptimisation would be initialising nextRoots with a capacity that's a factor of rootNodes.Count based on an estimate of the branch factor of your tree to head off resizing.

user1990587 · Accepted Answer · 2013-02-16 13:01:49Z

-1

You can return data in xml format from sql server database using for xml then bind it to treeview control.

answered Feb 16, 2013 at 13:01

user1990587

3864 silver badges15 bronze badges

2 Comments

millimoose Over a year ago

-1: that's not really what the OP is doing, he's munging some tree data he already has.

Nadeem Jamali Over a year ago

binding data is not a problem, but the actual problem is to add nodes (those I have in format of records/objects) to tree view and its branches on their right place.

Collectives™ on Stack Overflow

Replacing recursive with loop

3 Answers 3

Comments

2 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related