Review
Keep in mind I am using an older version of .NET so my semantics can be somehow verbose.
Navigation
You are lacking a reference back to the parent, which makes bottom-up navigation much harder. A tree that knows its parent allows for much more flexibility in navigation.
root.children.Add(new Tree()
{
id = node.id,
text = node.text,
children = null // <- no parent reference ;-(
});
public class Tree
{
public int? Id { get; set; }
public string Text { get; set; }
protected List<Tree> _children;
protected Tree _parent; // <- added reference to parent :-)
}
Now, we can use TreeExtensions to nagivate a tree. The most basic tree traversal walkers are available. More could be added if required.
public static class TreeExtensions
{
public static IEnumerable<Tree> Descendants(this Tree value) {
// a descendant is the node self and any descendant of the children
if (value == null) yield break;
yield return value;
// depth-first pre-order tree walker
foreach (var child in value.Children)
foreach (var descendantOfChild in child.Descendants()) {
yield return descendantOfChild;
}
}
public static IEnumerable<Tree> Ancestors(this Tree value) {
// an ancestor is the node self and any ancestor of the parent
var ancestor = value;
// post-order tree walker
while (ancestor != null) {
yield return ancestor;
ancestor = ancestor.Parent;
}
}
}
Lexicon
In computer science, many API's use the terminology below.
descendant: any child, grandchild, ..descendantOrSelf: any descendant or the specified node itselfancestor: any parent, grandparent, ..ancestorOrSelf: any ancestor or the specified node itself
However, I tend to use family tree terminology.
successor: any child, grandchild, ..descendant: any successor or the specified node itselfpredecessor: any parent, grandparent, ..ancestor: any predecessor or the specified node itself
Data Integrity
Encapsulating the family members _parent, _children provides us with the capability of preserving the tree's integrity.
public class Tree
{
public int? id { get; set; }
public string text { get; set; }
public List<Tree> children { get; set; }
}
public class Tree
{
public int? Id { get; set; }
public string Text { get; set; }
protected List<Tree> _children;
protected Tree _parent;
public Tree Parent { get { return _parent; } }
public Tree Root { get { return _parent == null ? this : _parent.Root; } }
public IEnumerable<Tree> Children {
get { return _children == null
? Enumerable.Empty<Tree>() : _children.ToArray();
}
}
}
We could then have Add and Remove support with sufficient validation support to maintain integrity.
public void Add(Tree child) {
if (child == null)
throw new ArgumentNullException();
if (child._parent != null)
throw new InvalidOperationException(
"A tree node must be removed from its parent before adding as child.");
if (this.Ancestors().Contains(child))
throw new InvalidOperationException("A tree cannot be a cyclic graph.");
if (_children == null) {
_children = new List<Tree>();
}
Debug.Assert(!_children.Contains(child), "At this point, the node is definately not a child");
child._parent = this;
_children.Add(child);
}
public bool Remove(Tree child) {
if (child == null)
throw new ArgumentNullException();
if (child._parent != this)
return false;
Debug.Assert(_children.Contains(child), "At this point, the node is definately a child");
child._parent = null;
_children.Remove(child);
if (!_children.Any())
_children = null;
return true;
}
Builder
I am not convinced an extension method is the way to go for this method. I would rather make a Builder class for it, but that's probably a matter of taste.
public static Tree BuildTree(this List<TreeNode> nodes)
{
// method impl ..
}
Determining the root node is not optimized. In one of your examples, there is a root in the input nodes. In another example, there is no root. If the former case, we could use that root as tree. In the latter, we could create the null-root.
// Create a NULL-root tree
Tree root = new Tree();
private static Tree FindTreeRoot(IList<TreeNode> nodes) {
var rootNodes = nodes.Where(node => node.parent == null);
if (rootNodes.Count() != 1) return new Tree();
var rootNode = rootNodes.Single();
nodes.Remove(rootNode);
return Map(rootNode);
}
private static Tree Map(TreeNode node) {
return new Tree {
Id = node.id,
Text = node.text,
};
}
Building the tree could then become a recursive action. I am using a list, in order to remove the visited nodes from the ones that still need to be visited.
public static Tree BuildTree(IEnumerable<TreeNode> nodes) {
if (nodes == null) return new Tree();
var nodeList = nodes.ToList();
var tree = FindTreeRoot(nodeList);
BuildTree(tree, nodeList);
return tree;
}
private static void BuildTree(Tree tree, IList<TreeNode> descendants) {
// Note: could be optimized further for performance
var children = descendants.Where(node => node.parent == tree.Id).ToArray();
foreach (var child in children) {
var branch = Map(child);
tree.Add(branch);
descendants.Remove(child);
}
foreach (var branch in tree.Children) {
BuildTree(branch, descendants);
}
}
Proposed Solution
This is an appendix of the classes used as an alternative/edited flow, with an example included.
public class Program
{
public static void Main()
{
//0 0 NULL
//1 1 0
//11 11 1
//2 2 0
//21 21 2
//211 211 21
//22 22 2
//3 3 0
var nodes = new List<TreeNode> {
new TreeNode { id = 0, text = "0", parent = null },
new TreeNode { id = 1, text = "1", parent = 0 },
new TreeNode { id = 11, text = "11", parent = 1 },
new TreeNode { id = 2, text = "2", parent = 0 },
new TreeNode { id = 21, text = "21", parent = 2 },
new TreeNode { id = 211, text = "211", parent = 21 },
new TreeNode { id = 22, text = "22", parent = 2 },
new TreeNode { id = 3, text = "3", parent = 0 }
};
var tree = TreeBuilder.BuildTree(nodes);
Console.ReadKey();
}
}
public class TreeNode
{
public int id { get; set; }
public string text { get; set; }
public int? parent { get; set; }
}
public static class TreeBuilder
{
public static Tree BuildTree(IEnumerable<TreeNode> nodes) {
if (nodes == null) return new Tree();
var nodeList = nodes.ToList();
var tree = FindTreeRoot(nodeList);
BuildTree(tree, nodeList);
return tree;
}
private static void BuildTree(Tree tree, IList<TreeNode> descendants) {
var children = descendants.Where(node => node.parent == tree.Id).ToArray();
foreach (var child in children) {
var branch = Map(child);
tree.Add(branch);
descendants.Remove(child);
}
foreach (var branch in tree.Children) {
BuildTree(branch, descendants);
}
}
private static Tree FindTreeRoot(IList<TreeNode> nodes) {
var rootNodes = nodes.Where(node => node.parent == null);
if (rootNodes.Count() != 1) return new Tree();
var rootNode = rootNodes.Single();
nodes.Remove(rootNode);
return Map(rootNode);
}
private static Tree Map(TreeNode node) {
return new Tree {
Id = node.id,
Text = node.text,
};
}
}
public static class TreeExtensions
{
public static IEnumerable<Tree> Descendants(this Tree value) {
// a descendant is the node self and any descendant of the children
if (value == null) yield break;
yield return value;
// depth-first pre-order tree walker
foreach (var child in value.Children)
foreach (var descendantOfChild in child.Descendants()) {
yield return descendantOfChild;
}
}
public static IEnumerable<Tree> Ancestors(this Tree value) {
// an ancestor is the node self and any ancestor of the parent
var ancestor = value;
// post-order tree walker
while (ancestor != null) {
yield return ancestor;
ancestor = ancestor.Parent;
}
}
}
public class Tree
{
public int? Id { get; set; }
public string Text { get; set; }
protected List<Tree> _children;
protected Tree _parent;
public Tree() {
Text = string.Empty;
}
public Tree Parent { get { return _parent; } }
public Tree Root { get { return _parent == null ? this : _parent.Root; } }
public int Depth { get { return this.Ancestors().Count() - 1; } }
public IEnumerable<Tree> Children {
get { return _children == null ? Enumerable.Empty<Tree>() : _children.ToArray(); }
}
public override string ToString() {
return Text;
}
public void Add(Tree child) {
if (child == null)
throw new ArgumentNullException();
if (child._parent != null)
throw new InvalidOperationException("A tree node must be removed from its parent before adding as child.");
if (this.Ancestors().Contains(child))
throw new InvalidOperationException("A tree cannot be a cyclic graph.");
if (_children == null) {
_children = new List<Tree>();
}
Debug.Assert(!_children.Contains(child), "At this point, the node is definately not a child");
child._parent = this;
_children.Add(child);
}
public bool Remove(Tree child) {
if (child == null)
throw new ArgumentNullException();
if (child._parent != this)
return false;
Debug.Assert(_children.Contains(child), "At this point, the node is definately a child");
child._parent = null;
_children.Remove(child);
if (!_children.Any())
_children = null;
return true;
}
id = null? ID's are used for identification between objects, but you can have multiple null ID's how are you going to differentiate those? \$\endgroup\$id = null, but may have multipleparent = nullindicating multiple root-level elements. I've updatedTreeNodeand changed the type ofidfromint?toint, and added examples. \$\endgroup\$idhere is just a unique identifier for a node in the forest for id-based lookup in the tree when required; it can be any unique series really.. \$\endgroup\$