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

public static Control FindChildControlByDepth(this Control Page, string ControlID, int depth)
        {
            if (depth > 10)
                throw new ArgumentException("Cannot search beyond a depth of 10", "depth"); 
            foreach (Control c in Page.Controls)
            {
                if (c.ID == ControlID)
                    return c;
                if (depth > 0)
                {
                    foreach (Control c1 in c.Controls)
                    {
                        if (c1.ID == ControlID)
                            return c1;
                        if (depth > 1)
                        {
                            foreach (Control c2 in c1.Controls)
                            {
                                if (c2.ID == ControlID)
                                    return c2;
                                if (depth > 2)
                                {
                                    foreach (Control c3 in c2.Controls)
                                    {
                                        if (c3.ID == ControlID)
                                            return c3;
                                        if (depth > 3)
                                        {
                                            foreach (Control c4 in c3.Controls)
                                            {
                                                if (c4.ID == ControlID)
                                                    return c4;
                                                if (depth > 4)
                                                {
                                                    foreach (Control c5 in c4.Controls)
                                                    {
                                                        if (c5.ID == ControlID)
                                                            return c5;
                                                        if (depth > 5)
                                                        {
                                                            foreach (Control c6 in c5.Controls)
                                                            {
                                                                if (c6.ID == ControlID)
                                                                    return c6;
                                                                if (depth > 6)
                                                                {
                                                                    foreach (Control c7 in c6.Controls)
                                                                    {
                                                                        if (c7.ID == ControlID)
                                                                            return c7;
                                                                        if (depth > 8)
                                                                        {
                                                                            foreach (Control c8 in c7.Controls)
                                                                            {
                                                                                if (c8.ID == ControlID)
                                                                                    return c8;
                                                                                if (depth > 9)
                                                                                {
                                                                                    foreach (Control c9 in c8.Controls)
                                                                                    {
                                                                                        if (c9.ID == ControlID)
                                                                                            return c9;
                                                                                    }
                                                                                }
                                                                            }
                                                                        }
                                                                    }
                                                                }
                                                            }
                                                        }
                                                    }

                                                }
                                            }
                                        }
                                    }
                                }
                            }
                        }
                    }

                }
            }
            return null;
        }

Answer 2

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));

Answer 3

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 4

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