Click here to Skip to main content
13,700,500 members
Click here to Skip to main content
Add your own
alternative version


39 bookmarked
Posted 11 Aug 2004

Generic Tree Container in C# 2.0

, 11 Aug 2004
Rate this:
Please Sign up or sign in to vote.
A small library implementing a generic tree container showing off generics and iterators.


With C# 2.0, a powerful language feature is being introduced which all C++ programmers have been missing since the beginnings of this altogether so cleanly and beautifully designed language: generics. This article uses this new feature to implement a generic tree class. Tree structures have more than just one natural way of being traversed, this is also a good motivation to demonstrate the use of C# 2.0's new iterator feature. If you wonder how you can build the code or how you can start trying out the new language features, go look at Microsoft's site where you can download a beta of their new Express line of developers products.


For a general introduction into the topic of generics and/or iterators, please take a look at the specification of C# 2.0 by Microsoft which does a good job on explaining them in detail.


When using the code, you will be dealing with two classes: Node and NodeCollection. Before going into the details of the implementation, it's probably a good idea to scan the demo project which comes with the source archive. The demo project is a console application which takes a single parameter. This parameter should be a path pointing to a directory. The demo first loads the file hierarchy rooted inside that path into an internally kept tree structure using the Node class, and then iterates over this tree structure once depth-first, then breadth-first. In the demo's Run() method, you see how to specialize the Node class for a given type, and construct an instance:

void Run(string rootdir)
    Node<string> root = new Node<string>(rootdir);

The code above creates an instance of the Node class specialized for containing data of type string and initializes the instance with a value. The Node class contains a property Data which allows read-only access to the element type for which it is specialized. Exactly this property is what you initialize in the constructor code. If you want to access the children of a node, you use the Children property which returns an instance of NodeCollection. Each node has a Parent property, too, which is read-only. If you add a node as the child of another, the first node's Parent property will reflect this change. Newly constructed nodes return null as their Parent, meaning they are located in the root of the hierarchy. The NodeCollection, on the other hand, has a read-only property Owner returning the Node whose children it contains. NodeCollection is not meant to be used as a general-purpose container for Nodes, thus its constructor is not publicly accessible. Node contains other useful properties and methods: the Root property gets the root of a node (wouldn't you have guessed ;-)), IsAncestorOf() takes another node and returns whether the instance node is an ancestor of the passed node, IsDescendantOf() checks for exactly the opposite condition, and DoesShareHierarchyWith() takes another node and returns whether the instance node and the passed node are equal or have an ancestor-descendant relationship (true) or not (false). GetDepthFirstEnumerator() and GetBreadthFirstEnumerator() return iterators performing a depth-first or breadth-first traversal. Note that the iterators returned by these methods iterate over the Data values of the nodes, not the nodes themselves, meaning that .Current will return the value of Data of the currently visited node.


The implementation of this small library makes use of two new features of C# 2.0: generics and iterators. Generics are used to allow the nodes to function as a type-safe container. Without them, the Data property would have to be of type object, requiring clients to cast to the correct type and allowing to instantiate Node with objects of different types. Iterators, on the other hand, are used for implementing depth-first and breadth-first traversal in a compellingly intuitive way. Let's take a look at their implementation:

public IEnumerator<Element> GetDepthFirstEnumerator()
    yield return mData;
    foreach (Node<Element> kid in mChildren)
        IEnumerator<Element> kidenumerator= kid.GetDepthFirstEnumerator();
        while (kidenumerator.MoveNext())
            yield return kidenumerator.Current;

IEnumerator<> is defined in System.Collections.Generic and defines a typesafe iterator, i.e., an iterator whose Current property is strongly typed.

Now, our depth-first traversal first returns the data of the current node itself, then iterates over the children nodes, gets their enumerators, and returns the values visited. For example, if you build up a structure like:

Node<string> root= new Node<string>("Gramps");
Node<string> son= new Node<string>("Son");
Node<string> daughter= new Node<string>("Daughter");
son.Children.Add(new Node<string>("Grandson"));
son.Children.Add(new Node<string>("Granddaughter"));

a call like:

foreach (string s in root.GetDepthFirstEnumerator())

will result in:


First, root.GetDepthFirstEnumerator() yields root's data, i.e., "Gramps"; then it starts iterating over its children, the first one being son. Now, son.GetDepthFirstEnumerator() gets called and yields its data "Son" before starting to iterate over its own children. Both children yield their data "Grandson" and "Granddaughter", but no more because they don't have children themselves. Now, son.GetDepthFirstEnumerator() is done, and root.GetDepthFirstEnumerator() goes on to daughter, which, having no children of its own, yields only its own data "Daughter".

Breadth-first traversal is a little more complicated, but still C# 2.0's iterator facility allows an incredibly easy implementation:

public IEnumerator<Element> GetBreadthFirstEnumerator()
    Queue<Node<Element>> todo = new Queue<Node<Element>>();
    while (0 < todo.Count)
        Node<Element> n = todo.Dequeue();
        foreach (Node<Element> kid in n.mChildren)
        yield return n.mData;

Assuming the same node structure as for the depth-first example, the code piece:

foreach (string s in root.GetBreadthFirstEnumerator())

produces this output:


In this case, recursion is unrolled into a loop. First, root.GetBreadthFirstEnumerator() creates a queue and puts root inside. Then, getting into the while loop, it unqueues root. Now, it iterates over root's children son and daughter and puts them into the queue. Then, it yields root's data "Gramps". Next time inside the loop, it pops son from the queue, pushes son's children into the queue, and yields son's data "Son". Next time, it pops daughter from the queue which has no children, so it yields daughter's data "Daugther" and proceeds. Now, it pops the two children of son, both of which don't have children of their own, thus do not add anything to the queue. Their data "Grandson" and "Granddaugther" gets yielded, and next time checking the loop-condition, the queue is empty and traversal thus finished.

Conclusion and To-Do

This little class gets you a generic tree container, if you need a quick and simple solution. It shows off the possibilities the new language features of C# 2.0 facilitate. In order to create a really useful, general purpose tree library, though, the code would have to be more adaptable to specific needs of the clients. Here's a short list of ideas - and who knows, maybe my next article will have some or even all of them implemented:

  • At the moment, Node is implemented for trees with an arbitrary number of children. But very often, you know that each node will have a fixed number of children (binary trees, quad trees etc.). For such scenarios, the presented implementation is clearly inefficient as it makes use internally of a framework container (System.Containers.Generic.List) where it should be using an array. So, it would be nice if nodes were parameterizable with a strategy for keeping children. Ideally, there would be two predefined strategies in the library, one using the list container, another one for arrays of static size, and clients could implement an interface for other cases.
  • Considering that quite often there is the need to visualize a tree structure, it would make sense to write an adaptor for filling a TreeView from a Node structure.
  • As for now, both traversal algorithms do not supply clients with any information about where exactly they are in the tree. Now, in game applications, for example, it's usually important to know how deep a depth-first traversal has gone currently. Besides, sometimes they want to parameterize how deep traversal will proceed, or they want to add nodes as they get deeper into the tree.


2004-08-10: first release.


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Another Old Guy
Chief Technology Officer
Austria Austria
Started with programming about 20 years ago as a teenager. Has been doing software-development for some 16 years now commercially.
Is interested in design and process. Language specifics are sometimes fun, but they're never here to stay.
simply loves MS' new toys, .NET and C#.

Had his own company for a while, creating games for a living Smile | :)

Nowadays more Ronin-style: doing contract work together with a few good friends...

You may also be interested in...

Comments and Discussions

QuestionMy problem [modified] Pin
DGyurka7-Mar-11 9:15
memberDGyurka7-Mar-11 9:15 
GeneralPassing other data structures into tree Pin
barts001-Oct-08 17:11
memberbarts001-Oct-08 17:11 
GeneralRe: Passing other data structures into tree Pin
sonamsingh_1929-Nov-08 5:10
membersonamsingh_1929-Nov-08 5:10 
GeneralRe: Passing other data structures into tree Pin
sonamsingh_1929-Nov-08 5:54
membersonamsingh_1929-Nov-08 5:54 
QuestionLicense question Pin
olbrin12-Jun-07 23:45
memberolbrin12-Jun-07 23:45 
AnswerRe: License question Pin
Max Hajek (aka AzazelDev)13-Jun-07 2:58
memberMax Hajek (aka AzazelDev)13-Jun-07 2:58 
GeneralRe: License question Pin
olbrin13-Jun-07 21:31
memberolbrin13-Jun-07 21:31 
Generalforeach sample doese not work for 2.0 Pin
lesta16-Jul-06 23:31
memberlesta16-Jul-06 23:31 
GeneralRe: foreach sample doese not work for 2.0 [modified] Pin
DmgInc28-Jul-06 2:38
memberDmgInc28-Jul-06 2:38 
GeneralRe: foreach sample doese not work for 2.0 [modified] Pin
samentu29-Apr-07 20:24
membersamentu29-Apr-07 20:24 
QuestionRe: foreach sample doese not work for 2.0 Pin
BurlingtonON24-Sep-07 3:43
memberBurlingtonON24-Sep-07 3:43 
QuestionRe: foreach sample doese not work for 2.0 Pin
BurlingtonON24-Sep-07 3:56
memberBurlingtonON24-Sep-07 3:56 
JokeCode Fix due to Changes in .NET 2.0 Pin
MonkeyCookie14-Sep-05 7:21
memberMonkeyCookie14-Sep-05 7:21 
GeneralRe: Code Fix due to Changes in .NET 2.0 Pin
shawnkaczmarek7-Dec-05 17:11
membershawnkaczmarek7-Dec-05 17:11 
GeneralRe: Code Fix due to Changes in .NET 2.0 Pin
dB.20-Dec-05 4:42
memberdB.20-Dec-05 4:42 
GeneralRe: Code Fix due to Changes in .NET 2.0 Pin
decoder7222-Nov-07 8:09
memberdecoder7222-Nov-07 8:09 
GeneralFurther Reading Pin
chrisv12-Aug-04 6:41
memberchrisv12-Aug-04 6:41 
GeneralRe: Further Reading Pin
AzazelDev aka Max Hajek12-Aug-04 22:33
memberAzazelDev aka Max Hajek12-Aug-04 22:33 
GeneralRe: Further Reading Pin
rveldman3-Dec-08 4:19
memberrveldman3-Dec-08 4:19 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web01-2016 | 2.8.180910.1 | Last Updated 12 Aug 2004
Article Copyright 2004 by Another Old Guy
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid