Recursive search on Node Tree with Linq and Queue

Question

I've created a Node class which contains two important properties:

• public Node Parent { get; private set; }
• private List<Node> Children { get; set;}

As the name suggests, the Parent object holds information about the ancestor of a certain node, if the parent is the root of the tree, then the parent is set to null. And the Children collection stores all the descendant nodes.

The methods responsible for the searching are:

• GetChildren()
• GetChildrenRecursive()

All of them are described on the code documentation. But I am specially concerned about the performance and reliability of the searching algorithm and the overall implementation of the tree structure. I'd like to hear some opinions on how I could possibly improve the code quality or any reading material about searching algorithms on trees.

• Node.cs

/// <summary>
/// Represents a tree-like structure
/// </summary>
public class Node
{
    /// <summary>
    /// The ancestor (parent) of this node. Null if the current node is the root of the tree.
    /// </summary>
    public Node Parent { get; private set; }

    /// <summary>
    /// The descendats (children) of this node.
    /// </summary>
    private List<Node> Children { get; set; }

    /// <summary>
    /// Checks wheter the current node is the root of the tree.
    /// </summary>
    public bool IsRoot { get { return Parent != null; } }

    /// <summary>
    /// Checks wheter the current node has any children.
    /// </summary>
    public bool HasChildren { get { return Count > 0; } }

    /// <summary>
    /// The current node's children count.
    /// </summary>
    public int Count { get { return Children?.Count ?? 0; } }

    /// <summary>
    /// The object stored in the current node.
    /// </summary>
    public object Value { get; set; }

    /// <summary>
    /// Creates a new instance of the <see cref="Node"/> class with an empty object.
    /// </summary>
    /// <param name="value">The value that will be held by this node</param>
    public Node()
    {
        Value = new object();
        Children = new List<Node>();
    }

    /// <summary>
    /// Creates a new instance of the <see cref="Node"/> class with a set value.
    /// </summary>
    /// <param name="value">The value that will be held by this node</param>
    public Node(object value)
    {
        Value = value;
        Children = new List<Node>();
    }

    /// <summary>
    /// Returns a copy of all values contained in this <see cref="Node"/>.
    /// <para>
    /// Useful for avoiding interferences between instances of the <see cref="Node"/> class.
    /// </para>
    /// </summary>
    /// <returns>A <see cref="Node"/> with the property values of this node</returns>
    public Node DeepCopy()
    {
        var other = (Node)MemberwiseClone();

        other.Children = new List<Node>(collection: Children);
        other.Parent = Parent?.DeepCopy();
        other.Value = new Node(value: Value);

        return other;
    }

    /// <summary>
    /// Adds a child to this <see cref="Node"/>.
    /// </summary>
    /// <param name="node">The node to be added</param>
    public void AddChild(Node node)
    {
        if (node != this && node.Parent == null)
        {
            node.Parent = this;

            Children.Add(node);
        }
    }

    /// <summary>
    /// Removes a child from this <see cref="Node"/>.
    /// </summary>
    /// <param name="node">The node to be removed</param>
    public void RemoveChild(Node node)
    {
        if (node != this && Children.Contains(node))
        {
            Children.Remove(node);
        }
    }

    /// <summary>
    /// Performs a superficial search, returning the children on the first level.
    /// </summary>
    /// <returns>An <see cref="IEnumerable{Node}"/>containing the search result</returns>
    public IEnumerable<Node> GetChildren()
    {
        return Children.AsEnumerable();
    }

    /// <summary>
    /// Performs a recursive search, returning all the children on all levels
    /// </summary>
    /// <returns>An <see cref="IEnumerable{Node}"/>containing the search result</returns>
    public IEnumerable<Node> GetChildrenRecursive()
    {         
        var root = DeepCopy();

        // No descendants have children. No recursion neeeded.
        if (root.Children.All(x => x.Children.Count == 0))
        {
            return GetChildren();
        }
        // Some (or all) descendants have children. Use recursion
        else
        {
            var allChildren = new List<Node>();
            var searchQueue = new Queue<Node>();

            // Adds the first generation of children into the queue
            GetChildren().ToList()
                .ForEach((x) => searchQueue.Enqueue(x));

            // Loops until the queue is empty
            while (searchQueue.Any())
            {
                // Adds the first children in the queue to the final collection
                allChildren.Add(searchQueue.Peek());

                // Checks if the first children in the queue has descendants
                if (searchQueue.Peek().HasChildren)
                {
                    // Adds the descendants of the children being searched on the queue
                    searchQueue.Peek().Children
                        .ForEach((x) => searchQueue.Enqueue(x));
                }

                // Removes the first node on the queue, since it has been searched already.
                searchQueue.Dequeue();
            }

            return allChildren;
        }
    }

    /// <summary>
    /// Override for the <code><see cref="object"/>.ToString()</code> method
    /// </summary>
    /// <returns>The string representation of this node's value</returns>
    public override string ToString()
    {
        return $"{Value?.ToString()}";
    }
}

Also, I'm including some tests I've made, all of them are passing as of now.

• NodeTest.cs

[TestClass]
public class NodeTest
{
    [TestMethod]
    public void Node_DeepCopy_CopySuccessful()
    {
        // Arrange
        var root = new Node(null);

        var node1 = new Node(null);
        var node2 = new Node(null);

        var copyNode = new Node(null);

        // Act
        root.AddChild(node1);
        root.AddChild(node2);

        copyNode = root.DeepCopy();
        var actual = copyNode.HasChildren;

        // Assert
        Assert.AreEqual(true, actual);
    }

    [TestMethod]
    public void Node_DeepCopy_CopyIsIndependent()
    {
        // Arrange
        var root = new Node(null);

        var node1 = new Node(null);
        var node2 = new Node(null);

        var copyNode = new Node(null);

        // Act
        root.AddChild(node1);
        root.AddChild(node2);

        copyNode = root.DeepCopy();
        root.AddChild(new Node(null));

        var actual = root.Count != copyNode.Count;

        // Assert
        Assert.AreEqual(true, actual);
    }

    [TestMethod]
    public void Node_Search_ReturnsAllElements()
    {
        // Arrange
        const int EXPECTED_CHILDREN_COUNT = 3;

        var root = new Node(null);

        var root_child1 = new Node(null);
        var root_child2 = new Node(null);
        var root_child3 = new Node(null);

        // Act
        root.AddChild(root_child1);
        root.AddChild(root_child2);
        root.AddChild(root_child3);

        int actual = root.Count;

        // Assert
        Assert.AreEqual(EXPECTED_CHILDREN_COUNT, actual);
    }

    [TestMethod]
    public void Node_RecursiveSearch_ReturnsAllElements()
    {
        // Arrange
        const int EXPECTED_CHILDREN_COUNT = 9;

        var root = new Node("Root node");

        var rc1 = new Node("[Gen 1] 1st child of: root");
        var rc2 = new Node("[Gen 1] 2nd child of: root");
        var rc3 = new Node("[Gen 1] 3rd child of: root");

        var rc2_1 = new Node("[Gen 2] 1st child of: root's 2nd child");
        var rc2_2 = new Node("[Gen 2] 2nd child of: root's 2nd child");
        var rc3_1 = new Node("[Gen 2] 1st child of: root's 3rd child");

        var rc2_1_1 = new Node("[Gen 3] 1st child of: root's 2nd child's 1st child");
        var rc3_1_1 = new Node("[Gen 3] 1st child of: root's 3rd child's 1st child");

        var rc3_1_1_1 = new Node("[Gen 4] 1st child of: root's 3rd child's 1st child's 1st child");

        // Act
        rc2_1.AddChild(rc2_1_1);
        rc2.AddChild(rc2_1);
        rc2.AddChild(rc2_2);

        rc3_1_1.AddChild(rc3_1_1_1);
        rc3_1.AddChild(rc3_1_1);
        rc3.AddChild(rc3_1);

        root.AddChild(rc1);
        root.AddChild(rc2);
        root.AddChild(rc3);

        int actual = new List<Node>(root.GetChildrenRecursive()).Count;

        // Assert
        Assert.AreEqual(EXPECTED_CHILDREN_COUNT, actual);
    }
}

Answer 1

Reading Material

.. any reading material about searching algorithms on trees

These are the most common tree walkers:

• Breadth-First Search
• Depth-First Search

---

Review

There is a bug with IsRoot. Also, why not provide a property Root { get; }?

if the parent is the root of the tree, then the parent is set to null

public bool IsRoot { get { return Parent != null; } }

You should also take advantage of the sweet syntactic sugar of the language (for all your properties):

 public bool IsRoot => Parent == null;

---

Since Children is private and you always instantiate a list, there is no reason to use null-propagation here:

public int Count { get { return Children?.Count ?? 0; } }

public int Count => Children.Count;

---

AddChild should throw exceptions on invalid input. You don't check for an invalid tree, what if the node is a grand-parent of the the current instance? Perform similar checks for RemoveChild.

public void AddChild(Node node)
{
    node = node ?? throw new ArgumentNullException(nameof(node));
    if (IsAncestorOrSelf(node)) // <- you should implement such method
        throw new ArgumentException("The node can not be an ancestor or self");
    if (IsDescendant(node)) // <- you should implement such method
        throw new ArgumentException("The node can not be a descendant");
    node.Parent = this;
    Children.Add(node);
}

---

GetChildren should return an immutable copy of the list containing the children.

public IEnumerable<Node> GetChildren()
{
    return Children.ToArray();
}

---

I don't know why you would need DeepCopy functionality.

---

GetChildrenRecursive should be called GetDescendants. I would implement it using recursion. This is implemented as depth-first (DFS).

public IEnumerable<Node> GetDescendants()
{
    foreach (var child in Children)
    {
         yield return child;
         foreach (var descendant in child.GetDescendants())
         {
              yield return descendant;
         }
    }
}

Answer 2

public Node DeepCopy()
{
    var other = (Node)MemberwiseClone();

    other.Children = new List<Node>(collection: Children);
    other.Parent = Parent?.DeepCopy();
    other.Value = new Node(value: Value);

    return other;
}

You should be careful when using this, because it actually clones the entire tree (via Parent and Children). Besides that, I think MemberwiseClone copies the Children and Parent recursively. So by creating a new list for the Children and calling DeepCopy() on the Parent you actually get a mix of copies and existing Node objects, that can lead to unexpected behavior if you change either the copy or the original later on. And the child instances (other) will not be part of the parents Children list in the copy.

Why does other.Value become a Node(Value)? - Value is by the way also covered by MemberwiseClone.

Consider if it is of any use and possibly skip it. I can't see any use of it?

---

public void RemoveChild(Node node)
{
    if (node != this && Children.Contains(node))
    {
        Children.Remove(node);
    }
}

It is safe to call Children.Remove(node) even if node is not in the list or is null, so you can omit the Contains() check. node != this - I suppose this should be avoided in the Add method - but why can't this be removed if provided as node? You could consider to return the bool values returned from Children.Remove(node), to let the client known if the operation was succesful or not.

---

You could consider to make the Node class generic:

public class Node<T>
{
    public T Value { get; }
    ...
}

---

As of GetChildrenRecursive() it seems to work, but looks rather complicated as a BFS algorithm. Remember that you have private access to the properties and fields of Node instances, so you can for instance call Children on any Node not just this. Below is a revised version, that is a little easier to follow:

  public IEnumerable<Node> GetChildrenRecursive()
  {
    if (!HasChildren) yield break;

    Queue<Node> queue = new Queue<Node>(this.Children);

    while (queue.Count > 0)
    {
      var node = queue.Dequeue();
      yield return node;

      if (node.HasChildren)
      {
        foreach (Node child in node.Children)
        {
          queue.Enqueue(child);
        }
      }
    }
  }

It uses yield return instead of creating a concrete List<Node> object which is more in line with the return value IEnumerable<Node>.