Ideas on building an indented structure from a List?

Question

I have a List (.NET) and need to build an indented tree structure. Each item in the list has a Position property indicating the level of indentation. The final structure should look something like this:

// (1) 1
//      (2) 1-1
//      (2) 1-2
//      (2) 1-3
// (1) 2
//      (2) 2-1
//          (3) 2-1-1
// (1) 3

The number inside the parentheses is the Position property. Each subsequent item at a given level should have a label indicated its count in the list of items at that level. Lower position levels will have sort of an outline format label, as shown in the sample. Keep in mind, I have to generate those labels correctly.

I honestly haven't done recursive work for a while and, although I'm thinking that will be the best solution, I'm just stuck on how to get the job done. I may be over-complicating it. My thinking is that when I get to a "leaf," I should remove that item from the list and return, but I'm not sure. Just spinning my wheels a bit.

Thanks, Jay

UPDATE:

Here's something close, but I'm having trouble figuring out the last case. So far, it does fine if the next item falls on the same level or is indented one level, but I need a case for when the next item in the list is in a position less than the current one (i.e., is indented farther to the left). Also, I'm not sure about my base case at the top of the method:

var sb = new StringBuilder();
BuildTree(sb, list, 0, 1, string.Empty);
return sb.ToString();

private void BuildTree(StringBuilder sb, List<Item> list, int currIndex, int count, string parentId)
{
    if (list.Count == currIndex)
    {
        return;
    }

    // Build my item.
    string currId = parentId == string.Empty ? count.ToString() : parentId + "-" + count;
    sb.Append(currId + "<br />");

    if (list[currIndex + 1].Position == list[currIndex].Position)
    {
        BuildTree(sb, list, currIndex + 1, count + 1, parentId);
    }

    if (list[currIndex + 1].Position > list[currIndex].Position)
    {
        BuildTree(sb, list, currIndex + 1, 1, currId);
    }
}

UPDATE:

An alternative implementation, but still failing for the case of a less-indented row:

private void BuildTree(StringBuilder sb, List<Item> list, int currIndex, int count, string parentId)
{
    if (list.Count == 0)
    {
        return;
    }

    // Build my item.
    string currId = parentId == string.Empty ? count.ToString() : parentId + "-" + count;
    sb.Append(currId + "<br />");

    if (list[currIndex + 1].Position == list[currIndex].Position)
    {
        BuildTree(sb, list, currIndex + 1, count + 1, parentId);
    }

    if (list[currIndex + 1].Position > list[currIndex].Position)
    {
        BuildTree(sb, list, currIndex + 1, 1, currId);
    }

    list.RemoveAt(currIndex);
}

UPDATE:

This is a hack, but it works. I'm basically building multiple sub-trees off the root. I'd prefer a proper solution rather than a hack, but this is my best attempt so far. Alternatives welcome:

var sb = new StringBuilder();
List<Person> list = GetTheList();
int cnt = 0;
while (list.Count > 0)
{
    BuildTree(sb, list, 0, ++cnt, string.Empty);
}

return sb.ToString();


private void BuildTree(StringBuilder sb, List<Person> list, int currIndex, int count, string parentId)
{
    // Build my item.
    string currId = parentId == string.Empty ? count.ToString() : parentId + "-" + count;
    sb.Append(currId + "<br />");

    if (list.Count > 1)
    {
        if (list[currIndex + 1].Position == list[currIndex].Position)
        {
            BuildTree(sb, list, currIndex + 1, count + 1, parentId);
        }

        if (list[currIndex + 1].Position > list[currIndex].Position)
        {
            BuildTree(sb, list, currIndex + 1, 1, currId);
        }
    }

    list.RemoveAt(currIndex);
}

Possible duplicate: http://stackoverflow.com/questions/66893/tree-data-structure-in-c-sharp — user194076, Jun 23 '12 at 19:40
I simplified my last solution a bit. I think this is the best I can do. I'm not sure there's a good pure recursive solution, but this one is pretty straightforward and I think it'll do the job just fine. — birdus, Jun 30 '12 at 20:17

score 1 · Accepted Answer · answered Jun 30 '12 at 20:19

var sb = new StringBuilder();
List<Person> list = GetTheList();
int cnt = 0;
// The loop is necessary to iterate over the root elements.
while (list.Count > 0)
{
    BuildTree(sb, list, 0, ++cnt, string.Empty);
}

return sb.ToString();


private void BuildTree(StringBuilder sb, List<Person> list, int currIndex, int count, string parentId)
{
    string currId = parentId == string.Empty ? count.ToString() : parentId + "-" + count;
    sb.Append(currId + "<br />");

    if (list.Count > 1)
    {
        if (list[currIndex + 1].Position == list[currIndex].Position)
        {
            BuildTree(sb, list, currIndex + 1, count + 1, parentId);
        }

        if (list[currIndex + 1].Position > list[currIndex].Position)
        {
            BuildTree(sb, list, currIndex + 1, 1, currId);
        }
    }

    list.RemoveAt(currIndex);
}

Julian · Answer 2 · 2012-06-23T20:53:26.260

Here is one option. It's nothing fancy, perhaps not even pretty, and there for sure aren't any sanity checking or error handling logic, but it supports the structure you illustrate.

Output should be similar to what you have at the top of your question, and it'll hopefully guide you in the right direction.

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    public class Program
    {
        private static readonly IndentedList indentedList = new IndentedList();

        static void Main()
        {
            Fill();
            indentedList.Items.ForEach(Print);
        }

        private static void Fill()
        {
            indentedList.Add(new Node()); // 1
            indentedList.Add(new Node()); // 2
            indentedList.Add(new Node()); // 3

            indentedList.Items[0].Add(new Node()); // 1-1
            indentedList.Items[0].Add(new Node()); // 1-2
            indentedList.Items[0].Add(new Node()); // 1-3

            indentedList.Items[1].Add(new Node()); // 2-1
            indentedList.Items[1].Children[0].Add(new Node()); // 2-1-1
        }

        private static void Print(Node node)
        {
            var indentation = new String('\t', node.IndentationLevel - 1);
            Console.WriteLine("{0}({1}) {2}", indentation, node.IndentationLevel, node);
            node.Children.ForEach(Print);
        }
    }

    public class IndentedList
    {
        private readonly Node superNode = new Node();

        public List<Node> Items { get { return superNode.Children; } }

        public void Add(Node node)
        {
            superNode.Add(node);
        }
    }

    public class Node
    {
        public int IndentationLevel { get { return parent == null ? 0 : parent.IndentationLevel + 1; } }
        public int Position { get { return parent.Children.IndexOf(this) + 1; } }
        public List<Node> Children { get; private set; }

        private Node parent;
        private bool IsRootNode { get { return parent.parent == null; } }

        public Node()
        {
            Children = new List<Node>();
        }

        public void Add(Node child)
        {
            child.parent = this;
            Children.Add(child);
        }

        public override string ToString()
        {
            return IsRootNode ? Position.ToString() : String.Format("{0}-{1}", parent, Position);
        }
    }
}

This seems a bit complicated. I think I'll continue to pursue the recursive solution. Although my last attempt is a bit of hack, I think it's the direction I want to head. Thanks. — birdus, Jun 25 '12 at 13:46
No problem. But 'a bit complicated'? By all means, people have different levels of skills (which of course is all fine), but these are just two pretty simple classes. Compared to your rather complex recursive stuff (and recursion _is_ hard), I'd say this one's a breeze... If you could tell me which parts you find complicated, I'd love to try explaining them better to you :-) — Julian, Jun 25 '12 at 13:53
Perhaps "complicated" was the wrong word. How about verbose? I prefer the pithy, economic, elegant, and succinct recursive solution, although I'm quite certain mine could be improved. I'm pretty sure a simple way of handling the case I'm missing exists. I'm just waiting for someone who is smarter than I am to enlighten me. — birdus, Jun 25 '12 at 16:17

Ideas on building an indented structure from a List?

2 Answers2