FInd Previous nodes in a Tree in C#

Question

I am trying to write a Function Previous(), to get the previous nodes of a Tree. The statement is: "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.Previous() to find the previous 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.Previous()."

The node class goes 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();
    }
}

I need to write an extension method like this:

using System;
using System.Linq;

public static class NodeExtensions
{
    public static Node Previous(this Node node)
    {
        // TODO Implement extension method here
        
    }
  
}

I have a test case:

using System;
using System.Text;
using NUnit.Framework;

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

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

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

Whatever I try, it either goes into an infinite loop, or just returns the root nodes instead of "all silblings". Can someone help me here?

Answer 1

I think this will work for you

public static class NodeExtensions
{
    public static Node Previous(this Node node)
    {
        if (node.Parent == null) { return null; }
        var brothers = (List<Node>) node.Parent.Children;
        var index = brothers.IndexOf(node);
        if(index == 0) 
        {
            return node.Parent;
        }
        else
        {
            var next = brothers[index - 1];
            while (next.Children.Any()) 
            {
                next = next.Children.Last();
            }
            return next;
        }
    }

}