Search tree, simplest method for traversing c#

Question

I need to be able to search a tree with arbitrary many children. It could look like this.

                                   P
                                /  |  \
                               C   C   C     layer 1
                             / | \
                            C  C  C          layer 2
                            |
                            C                layer 3
                          / | \
                         C  C  C             layer 4

With arbitrary many children in each C. Is it convinient to have a double linked list for each start node in layer 1? (In layer 1 the non expanding nodes might also ofcourse expand). I need to evaluate and work with every sub-tree.

Whats the simplest method? Or maybe some kind of depth first search/breadth first search is better? The tree is constructed on the fly.

thanks

Answer 1

The easiest way to do this is using recursion.

Let's assume that your tree stores items of type T, and that type implements IEquatable<T>.

Firstly, let's write a very basic tree class:

public sealed class Node<T>
{
    public Node(T value) { Value = value; }
    public T Value { get; }
    public IEnumerable<Node<T>> Children => _children;

    public void Add(Node<T> child)
    {
        _children.Add(child);
    }

    readonly List<Node<T>> _children = new List<Node<T>>();
}

Now we can write a method to search that tree using recursion very simply. This will return the first node containing the specified value if it was found, or null if no such node was found.

public static Node<T> Find<T>(Node<T> root, T target) where T: IEquatable<T>
{
    if (root.Value != null && root.Value.Equals(target))
        return root;

    foreach (var child in root.Children)
    {
        var found = Find(child, target);

        if (found != null)
            return found;
    }

    return null;
}

It's easy to adapt this to return ALL nodes that match the target:

public static IEnumerable<Node<T>> FindAll<T>(Node<T> root, T target) where T : IEquatable<T>
{
    if (root.Value != null && root.Value.Equals(target))
        yield return root;

    foreach (var child in root.Children)
    {
        var found = FindAll(child, target);

        foreach (var item in found)
            yield return item;
    }
}

For demo purposes, here's a compilable console application. It includes a makeTree() method which I'm using to make a tree of depth 4 where each node has 5 children.

Then it uses Find<T>(Node<T> root, T target) to recursively search the tree to find the specified target values. One will succeed, the other will fail:

using System;
using System.Collections.Generic;

namespace Demo
{
    public sealed class Node<T>
    {
        public Node(T value) { Value = value; }
        public T Value { get; }
        public IEnumerable<Node<T>> Children => _children;

        public void Add(Node<T> child)
        {
            _children.Add(child);
        }

        readonly List<Node<T>> _children = new List<Node<T>>();
    }

    class Program
    {
        static void Main()
        {
            var root = makeTree(1, 1, 4, 5);

            lookFor(root, "3.4");
            lookFor(root, "6.3");
        }

        static void lookFor<T>(Node<T> root, T target) where T: IEquatable<T>
        {
            var found = Find(root, target);
            Console.WriteLine(found != null ? $"Found {target}" : $"Did not find {target}");
        }

        public static Node<T> Find<T>(Node<T> root, T target) where T: IEquatable<T>
        {
            if (root.Value != null && root.Value.Equals(target))
                return root;

            foreach (var child in root.Children)
            {
                var found = Find(child, target);

                if (found != null)
                    return found;
            }

            return null;
        }

        static Node<string> makeTree(int id1, int id2, int depth, int nChildren)
        {
            var root = new Node<string>($"{id1}.{id2}");

            if (depth == 0)
                return root;

            for (int i = 0; i < nChildren; ++i)
                root.Add(makeTree(id1+1, i+1, depth-1, nChildren));

            return root;
        }
    }
}