How to find the next node in a tree?

Question

The problem goes like this:

We 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. Your task is to write 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 have this Node class:

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

The solution should be a extension method such as this

      public static Node Next(this Node node)
    {

    }

The code I tried:

  public static Node Next(this Node node)
    {
        var newNode = NextLargerElement(node, node.Data);

        return newNode;
    }

    public static Node res;
    public static Node NextLargerElementUtil(Node root, int x) 
    {
        if (root == null)
            return null;

        if (root.Data > x)
            if ((res == null || (res).Data > root.Data))
                res = root;

        foreach (var children in root.Children)
        {
            NextLargerElementUtil(children, x);
        }

        return res;
    }

    static Node NextLargerElement(Node root, int x)
    {
        res = null;

        NextLargerElementUtil(root, x);

        return res;
 }   

Here is a testing case:

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

Answer 1

You can use Equals to backtrack your current node position in the tree and return it's parent's next child, if any, if there is not one then you need to backtrack the current node parent position and so on:

public static Node Next(this Node node)
{
    if(node.Children != null && node.Children.Any())
    {
        return node.Children.First();
    }
    
    // "backtracking", also can be done recursively
    var parent = node.Parent;
    while(parent != null)
    {
        var returnNext = false; // return next element in Children if current is node
        foreach (var element in parent.Children)
        {
            if(returnNext)
            {
                return element;
            }
            
            if(element == node)
            {
                returnNext = true;
                node = parent; // to find parent's position if there is no next child
            }
        }
        parent = parent.Parent;
    }
    
    return null;
}