How do I print out a tree structure in C#?

Question

I want to print a non-binary tree structure in a preorder non-recursive fashion. I have the following code- I want to increment the count as the code encounters children and sub-children of the root element.

public static void PrintTree(Node tree)
{
    List<Node> firstStack = new List<Node>();
    firstStack.Add(tree);

    List<List<Node>> childListStack = new List<List<Node>>();
    childListStack.Add(firstStack);

    while (childListStack.Count > 0)
    {
        List<Node> childStack = childListStack[childListStack.Count - 1];

        if (childStack.Count == 0)
        {
            childListStack.RemoveAt(childListStack.Count - 1);
        }
        else
        {
            tree = childStack[0];
            childStack.RemoveAt(0);

            string indent = "";
            for (int i = 0; i < childListStack.Count - 1; i++)
            {
                indent += (childListStack[i].Count > 0) ? "|  " : "   ";
            }

            Console.WriteLine(indent + "+- " + tree.Name);

            if (tree.Children.Count > 0)
            {
                childListStack.Add(new List<Node>(tree.Children));
            }
        }
    }
}

The output I am getting is-

+- root
   +- branch-A
   |  +- sibling-X
   |  |  +- grandchild-A
   |  |  +- grandchild-B
   |  +- sibling-Y
   |  |  +- grandchild-C
   |  |  +- grandchild-D
   |  +- sibling-Z
   |     +- grandchild-E
   |     +- grandchild-F
   +- branch-B
      +- sibling-J
      +- sibling-K

The output I need is-

1 branch-A
2 sibling-X
3 grandchild-A
3 grandchild-B
2 sibling-Y
3 grandchild-C
3 grandchild-D
2 sibling-Z
3 grandchild-E
3 grandchild-F
1 branch-B
2 sibling-J
2 sibling-K

Any help would be appreciated.

Answer 1

This type of traversal is known as Depth First traversal. The idea here is to go as deep as possible till you reach a leaf node. Then, repeat the process for the remaining children, for all unexplored nodes.

However, this is actually pretty easy to implement with a Stack. Now, in order to know the current level you are on, you need to keep track of each node level (this is because after reaching a leaf, you must return to the next node that shares the minimum amount of ancestors with the current node and that hasn't been explored yet. Since the next node you need to print can be at any level equal or less than the previous node, you have no way of knowing unless you keep track of them.

You can do so the following way:

        public static void PrintTree2(Node tree)
        {
            Stack<Node> stack = new Stack<Node>();
            Stack<int> nodeLevel = new Stack<int>();
            stack.Push(tree);
            nodeLevel.Push(1);

            while (stack.Count > 0)
            {
                Node next = stack.Pop();
                int curLevel = nodeLevel.Pop();
                Console.WriteLine(curLevel + " " + next.Name);

                foreach (Node c in next.Children)
                {
                    nodeLevel.Push(curLevel + 1);
                    stack.Push(c);
                }
            }
        }

Answer 2

Well, that looks familiar :wink:

The original algorithm keeps a stack of child lists in order to avoid blowing out the function call stack. With that in place, you can get the depth of a given node by checking the current length of the childListStack (and remove everything having to do with the indent string).

Without Recursion

public static void PrintTree(Node tree)
{
    List<Node> firstStack = new List<Node>();
    firstStack.Add(tree);

    List<List<Node>> childListStack = new List<List<Node>>();
    childListStack.Add(firstStack);

    while (childListStack.Count > 0)
    {
        List<Node> childStack = childListStack[childListStack.Count - 1];

        if (childStack.Count == 0)
        {
            childListStack.RemoveAt(childListStack.Count - 1);
        }
        else
        {
            tree = childStack[0];
            childStack.RemoveAt(0);

            Console.WriteLine((childListStack.Count - 1) + " " + tree.Name);

            if (tree.Children.Count > 0)
            {
                childListStack.Add(new List<Node>(tree.Children));
            }
        }
    }
}

This will output:

0 root
1 branch-A
2 sibling-X
3 grandchild-A
3 grandchild-B
2 sibling-Y
3 grandchild-C
3 grandchild-D
2 sibling-Z
3 grandchild-E
3 grandchild-F
1 branch-B
2 sibling-J
2 sibling-K

With Recursion

That said, this is much simpler to solve using classic recursion. You just need to increment the depth when you traverse into child nodes, which will output the same result.

public static void PrintTree(Node tree, int depth = 0)
{
    Console.WriteLine(depth + " " + tree.Name);

    for (int i = 0; i < tree.Children.Count; i++)
    {
        PrintTree(tree.Children[i], depth + 1);
    }
}

Answer 3

with help of Dictionaries and also queues, you can print nodes and their depths correctly. here comes an example:

    public static void PrintTree(BinaryTree root)
    {
        var q = new Queue<(BinaryTree node, int depth)>();
        q.Enqueue((root, 0));
        Dictionary<int, int> nodesValueDepth = new Dictionary<int, int>();

        while (q.Count > 0)
        {
            var currentNode = q.Dequeue();
            var currentDepth = currentNode.depth + 1;
            nodesValueDepth.Add(currentNode.node.value, currentNode.depth);
            if (currentNode.node.left != null)
            {
                q.Enqueue((currentNode.node.left, currentDepth));
            }
            if (currentNode.node.right != null)
            {
                q.Enqueue((currentNode.node.right, currentDepth));
            }
        }

        var maxDepth = nodesValueDepth.Values.Max();
        for (int i = 0; i <= maxDepth; i++)
        {
            if (i > 0)
            {
                Console.WriteLine("|");
            }
            Console.WriteLine(string.Join('-', nodesValueDepth.Where(a => a.Value == i).Select(a => a.Key).ToList()));
        }
    }