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

• Stacklysm: @dfhwze I'm sure there is a better/faster alternative to my approach to this.
• Stacklysm: @dfhwze Thinking now, If I don't find anything related to it in the MS assemblies, I'll just remove the tag
• Stacklysm: @dfhwze removed it
• dfhwze: meanwhile, I answered your question :) Btw, good to see unit tests in a question.

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

• Stacklysm: Thank you for taking your time and reviewing the code. Apparently I was paranoid that my first implementation of this method would mess up with the original object. I fixed the following: A) IsRoot code (now, if the parent is not set, then it's considered as the root Parent == null; B) Removed the null check on Children; C) Search method now returns immutable copies of the descendants
• dfhwze: I used recursion in GetDescendants because you have tagged your question as such. It is also possible without. I am sure someone will review that part.
• Stacklysm: Ok. About the addition of new children, I'm doing the following check: return !node.Children.Contains(this) && node != this && !Children.Contains(node);. If it's false, then ArgumentException is thrown.
• dfhwze: Once this question has sufficient answers, you can always ask a follow-up question with the new code. I will be happy review that question as well. For now, I can say, this new check does not cover all edge cases :)
• Stacklysm: I was worried about changing the code (which isn't allowed here). As you said, once there are sufficient suggestions, I'll do a follow-up. And again, thanks for you time spent into this matter :)

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>.

• dfhwze: I think he meant GetChildrenRecursive as search function :) btw I reached my vote limit of today :(
• Stacklysm: @Henrik Hansen GetChildrenRecursive() is the method I'm talking about, if you are doing this because I got something mixed up (I can't blame you), then that went completely over my head. As of the DeepCopy(Node), I removed it, there was no use to it. And I'm planning to make this a generic type, I used the object type because gave more freedom over what can be inserted in the tree.
• Stacklysm: And I will remove the null check when removing nodes
• dfhwze: Node<T> can always be used as Node<object> if you need to. So making it generic can't hurt your design.