Unable to search all the tree nodes in C#

Question

I have a tree that is built using the class Node where an instance of the class represents a node in the tree. For simplicity, the node has a single data field of type int.

the extension method NodeExtensions.Next() to find the next element in the tree. You can write as many helper methods as you want, but don't change the signature of the extension method NodeExtensions.Next().

I'm unable to go back to Node 2 and then move to the child node 3. Please help me in the algorithm.

The Node class looks like this:

public class Node
{
    private List<Node> _children;

    public Node(int data, params Node[] nodes)
    {
        Data = data;
        AddRange(nodes);
    }

    public Node Parent { get; set; }

    public IEnumerable<Node> Children
    {
        get
        {
            return _children != null
                ? _children
                : Enumerable.Empty<Node>();
        }
    }

    public int Data { get; private set; }

    public void Add(Node node)
    {
        Debug.Assert(node.Parent == null);

        if (_children == null)
        {
            _children = new List<Node>();
        }

        _children.Add(node);
        node.Parent = this;
    }

    public void AddRange(IEnumerable<Node> nodes)
    {
        foreach (var node in nodes)
        {
            Add(node);
        }
    }

    public override string ToString()
    {
        return Data.ToString();
    }
}

Test Method

[Test]
    public void Test()
    {
        // Test tree:
        // 
        // 1
        // +-2
        //   +-3
        //   +-4
        // +-5
        //   +-6
        //   +-7
        //
        var root = new Node(
            1,
            new Node(
                2,
                new Node(3),
                new Node(4)),
            new Node(
                5,
                new Node(6),
                new Node(7)));

        // Expected output:
        //
        // 1
        // 2
        // 3
        // 4
        // 5
        // 6
        // 7
        //
        var n = root;
        while (n != null)
        {
            Console.WriteLine(n.Data);
            n = n.Next();
        }

        // Test
        //
        n = root;
        Assert.AreEqual(1, n.Data);
        n = n.Next();
        Assert.AreEqual(2, n.Data);
        n = n.Next();
        Assert.AreEqual(3, n.Data);
        n = n.Next();
        Assert.AreEqual(4, n.Data);
        n = n.Next();
        Assert.AreEqual(5, n.Data);
        n = n.Next();
        Assert.AreEqual(6, n.Data);
        n = n.Next();
        Assert.AreEqual(7, n.Data);
        n = n.Next();
        Assert.IsNull(n);
    }

My Code

public static Node Next(this Node node)
    {
    
        if(node != null && node.Children != null && node.Children.Count() > 0)
        {
            for(int i = 0; i < node.Children.Count(); i++)
            {
               foreach(var child in node.Children)
               {
                 child.Next();
                 return child;
               }
            }
        }
        else{
            return null;
        }
   
    }

Output of my code
1
2
3

Expected Output Should be

1
2
3
4
5
6
7

Answer 1

This works and passes your test. I'm assuming you can't change the Node class.

public static Node Next(this Node node)
    {
        if (node.Children.Any())
            return node.Children.First();

        var parent = node.Parent;
        while (parent != null)
        {
            var nextNode = parent.Children.FindChildAfter(node);
            if (nextNode == null)
            {
                node = parent;
                parent = parent.Parent;
            }
            else
                return nextNode;
        }

        return null;
    }

    public static Node FindChildAfter(this IEnumerable<Node> items, Node item)
    {
        bool found = false;
        foreach (var it in items)
        {
            if (found) return it;
            if (ReferenceEquals(it, item)) 
                found = true;
        }

        return null;
    }

FindChildAfter is inefficient because it has to iterate through the entire collection each time. There would be better ways of structuring it so this isn't the case.

Answer 2

As an alternative approach you could consider having Node implement IEnumerable<Node>. If you do that then you just need to implement these two methods:

public IEnumerator<Node> GetEnumerator()
{
    yield return this;
    foreach (var child in Children)
        foreach (var x in child)
            yield return x;
}

IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

Now it is trivial to traverse your nodes:

var data = root.Select(x => x.Data).ToArray();

THat gives me an array with 1, 2, 3, 4, 5, 6, 7.