Categories: C#

In the previous post, I talked about doing a DFS on a rooted tree using the C# foreach loop/iterator concept.  In this post, I will discuss a different technique that is more function-based.

A common task on a tree is to traverse it in some defined order – pre-order, level-order, post-order, etc.  When we visit a node, we’d like to perform some action on it.  We can use delegates in C# (reference to a function) and lambdas to make this really compact and elegant:

public static void VisitDfs(TreeNode node, Action<TreeNode> func)
{
    if (func != null)
        func(node);
    foreach (TreeNode child in Children)
    {
        VisitDfs(child, func);
    }
}

If you pass in the root node to this method, you can call the function you send in on each node in that order.  You can apply this concept for other traversal patterns too:

public static void VisitBfs(TreeNode node, Action<TreeNode> func)
{
    Queue<TreeNode> q = new Queue<TreeNode>();
    q.Enqueue(node);
    while (q.Count > 0) 
    {
        node = q.Dequeue();
        if (func != null)
            func(node);
        foreach (TreeNode child in Children)
        {
            q.Enqueue(child);
        }
    }
}

This performs a breadth-first traversal (also called a ‘level order’ traversal with trees), calling the specified function at each node visit.

Here’s a sample usage of the DFS to count the number of leaves in a tree:

public static int CountLeaves(TreeNode root)
{
    int leafCount = 0;
    VisitDfs(root, node => {
        if (node.Children.Count == 0) {
            leafCount++;
        }
    });

    return leafCount;
}

No Comments