Recursively traversing a tree in C# from top down by row

Question

Interesting problem posed by a friend recently: Imagine you've got a List< NodeType > of all nodes in a tree. How would you go about traversing down the tree from the root node, by row such that you find the first node with a specific value. So say that each node has 3 attributes: its name/location, the identity of its parent, and who "owns" the node. The problem is you want to find the highest node in the tree that you "own" no matter what branch its on. I understand the basic logic in so much as to find the first set of children you look for all nodes with a parent set as the first node. But how would you go about recursively search through a List<> of nodes to find the highest node you own?

Answer 1

You’re looking for breadth-first search. It is normally implemented using a queue:

public Node FindFirstByBreadthFirst(this Node node, Predicate<Node> match)
{
    var queue = new Queue<Node>();
    queue.Enqueue(tree.RootNode);

    while (queue.Count > 0)
    {
        // Take the next node from the front of the queue
        var node = queue.Dequeue();

        // Process the node 'node'
        if (match(node))
            return node;

        // Add the node’s children to the back of the queue
        foreach (var child in node.Children)
            queue.Enqueue(child);
    }

    // None of the nodes matched the specified predicate.
    return null;
}

Answer 2

Algorithm:

Put the root node in a queue.

Repeat
    Take item from queue;
    Matching?  return Item
    Add all children to the queue
Until Queue is empty