Tree traversal

Tree traversal is the process of visiting each node in a tree data structure. This is often used to search for nodes within a tree. Well known algorithms are:

• Breadth-first search (BFS): This algorithm explores the neighbor nodes first, before visiting the child nodes.
• Depth-first search (DFS): This algorithm visits child nodes along a branch as far as possible before exploring neighbor nodes.

Both algorithms can be further classified by the order on how the nodes are visited.

This page describes a generic but simple C# implementation for both algorithms. They should work well for small trees. Working with larger trees might perform better when using a more sophisticated algorithm which considers the characteristics of the tree.

Implementation

public static IEnumerable<T> BreadthFirstSearch<T>(T item, 
        Func<T, IEnumerable<T>> childSelector)
{
    var queue = new Queue<T>();
    queue.Enqueue(item);
    while (queue.Any())
    {
        var next = queue.Dequeue();
        yield return next;
        foreach (var child in childSelector(next) ?? Enumerable.Empty<T>()) 
        { 
            queue.Enqueue(child); 
    	}
    }
}

public static IEnumerable<T> DepthFirstSearch<T>(T item, 
        Func<T, IEnumerable<T>> childSelector)
{
    var stack = new Stack<T>();
    stack.Push(item);
    while (stack.Any())
    {
        var next = stack.Pop();
        yield return next;
        foreach (var child in childSelector(next)?.Reverse() ?? Enumerable.Empty<T>()) 
        { 
            stack.Push(child); 
    	}
    }
}

The two methods traverse the tree and return a sequence of nodes via IEnumerable. This allows to use LINQ queries or their extension methods for any kind of search operation.

The childSelector is a delegate which returns the children collection of the node.

Sample code

The sample code uses the following tree. The path shown in the image is how the DFS algorithm visits the nodes.

internal static void Main()
{
    var root = 
        new Node("F", new[] {
            new Node("B", new[] {
                new Node("A"),
                new Node("D", new[] {
                    new Node("C"),
                    new Node("E")
                })
            }),
            new Node("G", new[] {
                new Node("I", new[] {
                    new Node("H")
                })
            })
        });
		
    // BFS: F, B, G, A, D, I, C, E, H
    Console.WriteLine("BFS: " + string.Join(", ", 
        BreadthFirstSearch(root, node => node.Children)));
    // DFS: F, B, A, D, C, E, G, I, H
    Console.WriteLine("DFS: " + string.Join(", ", 
        DepthFirstSearch(root, node => node.Children)));
}
    
public class Node
{
    public Node(string name, IEnumerable<Node> children = null)
    {
        Name = name;
        Children = children;
    }

    public string Name { get; }    	
    public IEnumerable<Node> Children { get; }    	
    public override string ToString() => Name;
}