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

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

Answer 2

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 3

Update: Haha, wow, this is completely wrong, I just realized (as in it is not doing what you asked for). Never mind -- looks like you already got a correct answer, anyway :)

---

I think I understand your problem. Let me know if I'm getting something wrong.

You have a NodeType class that looks something like this:

class NodeType
{
    public string Name { get; }
    public NodeType Parent { get; }
    public int OwnderId { get; }
}

First order of business would be to write a function that takes a NodeType parameter and, given some enumerable collection of NodeType objects, returns all of its descendents in a recursive fashion:

IEnumerable<NodeType> GetNodeChildren(NodeType node, IEnumerable<NodeType> nodes)
{
    var children = nodes.Where(n => n.Parent == node);

    if (children.Any())
    {
        foreach (NodeType child in children)
        {
            yield return child;

            var grandchildren = GetNodeChildren(child);
            foreach (NodeType grandchild in grandchildren)
            {
                yield return grandchild;
            }
        }
    }
}

Next up: write a function that takes a NodeType object and finds the highest descendent with a specified OwnerId. This is really a pretty simple operation, so I won't even define a proper function; I'll just use a lambda:

Func<NodeType, int, NodeType> findHighestDescendent = (node, id) => {
    return GetNodeChildren(node).FirstOrDefault(child => child.OwnerId == id);
};

Now for any given Id value, it is quite trivial to find the highest matching NodeType:

int id = 10; // just for example

NodeType highestOwnedNode = nodes
    .Select(n => findHighestDescendent(n, id))
    .FirstOrDefault(n => (n != null));