How do I print out a tree structure?

Question

I'm trying to improve performance in our app. I've got performance information in the form of a tree of calls, with the following node class:

public class Node
{
    public string Name; // method name
    public decimal Time; // time spent in method
    public List<Node> Children;
}

I want to print out the tree such that I can see lines between the nodes - something like in this question. What's an algorithm I can use in C# for doing that?

Edit: Obviously I need to use recursion - but my attempts keep putting the lines in the wrong places. What I'm asking for is a specific algorithm that will print the tree in a nice manner - the details of when to print a vertical line and when to print a horizontal one.

Edit: It isn't sufficient just to use copies of a string to indent the nodes. I'm not looking for

A
|-B
|-|-C
|-|-D
|-|-|-E
|-F
|-|-G

it has to be

A
+-B
| +-C
| +-D
|   +-E
+-F
  +-G

or anything similar, so long as the tree structure is visible. Notice that C and D are indented differently to G - I can't just use a repeated string to indent the nodes.

Knop

Here are some other answers to a printed binary tree that should help future visitors to this question: https://mcmap.net/q/125476/-how-to-print-binary-tree-diagram-in-java/198348. Particularly helpful is the one that prints out the tree horizontally. – Timbale

vanya.jp.net/vtree – Worden

Answer 1

The trick is to pass a string as the indent and to treat the last child specially:

class Node
{    
   public void PrintPretty(string indent, bool last)
   {
       Console.Write(indent);
       if (last)
       {
           Console.Write("\\-");
           indent += "  ";
       }
       else
       {
           Console.Write("|-");
           indent += "| ";
       }
       Console.WriteLine(Name);

       for (int i = 0; i < Children.Count; i++)
           Children[i].PrintPretty(indent, i == Children.Count - 1);
   }
}

If called like this:

root.PrintPretty("", true);

will output in this style:

\-root
  \-child
    |-child
    \-child
      |-child
      |-child
      \-child
        |-child
        |-child
        | |-child
        | \-child
        |   |-child
        |   |-child
        |   |-child
        |   \-child
        |     \-child
        |       \-child
        \-child
          |-child
          |-child
          |-child
          | \-child
          \-child
            \-child

Zed

What i can't figure out is how to not have the initial \- (or |-- , or └──, depending on your ascii preferences). – Nevins

In case anyone is interested in replacing "\-" etc, s @IanBoyd mentioned, here is how you do it: https://mcmap.net/q/330201/-c-display-a-binary-search-tree-in-console – Bevins

Answer 2

With Recursion

You'll need to keep track of an indentation string that's modified as you go deeper into the tree. To avoid adding extra | characters, you'll also need to know whether the Node is the last child in that set.

public static void PrintTree(Node tree, String indent, Bool last)
{
    Console.Write(indent + "+- " + tree.Name);
    indent += last ? "   " : "|  ";

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

When called like this:

PrintTree(node, "", true)

It will output text like this:

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

Without Recursion

If you happen to have a very deep tree and your call stack size is limited, you can instead do a static, non-recursive tree traversal to output the same result:

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

Hyperploid

Very nice and elegant. I made a generic version from your answer. – Qp

Answer 3

Create PrintNode method and use recursion:

class Node
{
    public string Name;
    public decimal Time;
    public List<Node> Children = new List<Node>();

    public void PrintNode(string prefix)
    {
        Console.WriteLine("{0} + {1} : {2}", prefix, this.Name, this.Time);
        foreach (Node n in Children)
            if (Children.IndexOf(n) == Children.Count - 1)
                n.PrintNode(prefix + "    ");
            else
                n.PrintNode(prefix + "   |");
    }
}

ANd then to print the whole tree just execute:

topNode.PrintNode("");

In my example it would give us something like that:

 + top : 123
   | + Node 1 : 29
   |   | + subnode 0 : 90
   |   |     + sdhasj : 232
   |   | + subnode 1 : 38
   |   | + subnode 2 : 49
   |   | + subnode 8 : 39
   |     + subnode 9 : 47
     + Node 2 : 51
       | + subnode 0 : 89
       |     + sdhasj : 232
       | + subnode 1 : 33
         + subnode 3 : 57

Yarber

That doesn't draw the tree, it just indents using copies of "|--". I want to be able to see the tree, so the algorithm has to leave gaps. – Knop

Sorry, but I don't understand what are you talking about. It does something similar to what was on example you gave. What exactly do you want to achieve? What "gaps"? – Yarber

OK, I gave you another example. What I wrote is just the main concept, think a little bit on your own and use it to your purposes. The idea is the same, but you just need to think of good, "smart" way of using it. Good luck! – Yarber

So you need to add some routines, that will format the prefix string for you. Play a little with it, I'm sure it will work – Yarber

Closer - it just needs to omit the pipes on the ones that don't continue. That was the bit that I got particularly stuck on. – Knop

I've edited the code again. It is closer (not exactly, what you need, but in good direction). – Yarber

Answer 4

Here is a variation on the (currently-accepted) answer by @Will. The changes are:

1. This uses Unicode symbols instead of ASCII for a more pleasing appearance.
2. The root element is not indented.
3. The last child of a group has a 'blank' line added after it (makes it easier to visually parse).

Presented as pseudo-code for easier consumption outside of C++:

def printHierarchy( item, indent )
  kids = findChildren(item)  # get an iterable collection
  labl = label(item)         # the printed version of the item
  last = isLastSibling(item) # is this the last child of its parent?
  root = isRoot(item)        # is this the very first item in the tree?

  if root then
    print( labl )
  else
    # Unicode char U+2514 or U+251C followed by U+2574
    print( indent + (last ? '└╴' : '├╴') + labl )

    if last and isEmpty(kids) then
      # add a blank line after the last child
      print( indent ) 
    end

    # Space or U+2502 followed by space
    indent = indent + (last ? '  ' : '│ ')
  end

  foreach child in kids do
    printHierarchy( child, indent )
  end
end

printHierarchy( root, "" )

Sample result:

Body
├╴PaintBlack
├╴CarPaint
├╴Black_Material
├╴PaintBlue
├╴Logo
│ └╴Image
│
├╴Chrome
├╴Plastic
├╴Aluminum
│ └╴Image
│
└╴FabricDark

Chesty

Answer 5

i am using the following method to print a BST

private void print(Node root, String prefix) {
    if (root == null) {
    System.out.println(prefix + "+- <null>");
    return;
    }

    System.out.println(prefix + "+- " + root);
    print(root.left, prefix + "|  ");
    print(root.right, prefix + "|  ");
}

Following is the output.

+- 43(l:0, d:1)
|  +- 32(l:1, d:3)
|  |  +- 10(l:2, d:0)
|  |  |  +- <null>
|  |  |  +- <null>
|  |  +- 40(l:2, d:2)
|  |  |  +- <null>
|  |  |  +- 41(l:3, d:0)
|  |  |  |  +- <null>
|  |  |  |  +- <null>
|  +- 75(l:1, d:5)
|  |  +- 60(l:2, d:1)
|  |  |  +- <null>
|  |  |  +- 73(l:3, d:0)
|  |  |  |  +- <null>
|  |  |  |  +- <null>
|  |  +- 100(l:2, d:4)
|  |  |  +- 80(l:3, d:3)
|  |  |  |  +- 79(l:4, d:2)
|  |  |  |  |  +- 78(l:5, d:1)
|  |  |  |  |  |  +- 76(l:6, d:0)
|  |  |  |  |  |  |  +- <null>
|  |  |  |  |  |  |  +- <null>
|  |  |  |  |  |  +- <null>
|  |  |  |  |  +- <null>
|  |  |  |  +- <null>
|  |  |  +- <null>

Popularly

pretty good @KSC, by far the best method to me for BST. I'll just leave out the output for null's. – Fasciation

Answer 6

This is a generic version of Joshua Stachowski's answer. The good thing about Joshua Stachowski's answer is that it doesn't require the actual node class to implement any extra method and it looks nice as well.

I made his solution generic which can be used for any type without modifying the code.

    public static void PrintTree<T>(T rootNode,
                                    Func<T, string> nodeLabel, 
                                    Func<T, List<T>> childernOf)
            {
                var firstStack = new List<T>();
                firstStack.Add(rootNode);

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

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

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

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

                        Console.WriteLine(indent + "+- " + nodeLabel(rootNode));
                        var children = childernOf(rootNode);
                        if (children.Count > 0)
                        {
                            childListStack.Add(new List<T>(children));
                        }
                    }
                }
            }

Usage

 PrintTree(rootNode, x => x.ToString(), x => x.Children);

Qp

Answer 7

The best way with full optionality without using recursion is` https://github.com/tigranv/Useful_Examples/tree/master/Directory%20Tree

public static void DirectoryTree(string fullPath)
    {
    string[] directories = fullPath.Split('\\');
    string subPath = "";
    int cursorUp = 0;
    int cursorLeft = 0;

    for (int i = 0; i < directories.Length-1; i++)
    {
        subPath += directories[i] + @"\";
        DirectoryInfo directory = new DirectoryInfo(subPath);
        var files = directory.GetFiles().Where(f => !f.Attributes.HasFlag(FileAttributes.Hidden)).Select(f => f.Name).ToArray();
        var folders = directory.GetDirectories().Where(f => !f.Attributes.HasFlag(FileAttributes.Hidden)).Select(f => f.Name).ToArray();             
        int longestFolder = folders.Length != 0 ? (folders).Where(s => s.Length == folders.Max(m => m.Length)).First().Length:0;
        int longestFle = files.Length != 0? (files).Where(s => s.Length == files.Max(m => m.Length)).First().Length : 0;
        int longestName =3 + (longestFolder <= longestFle ? longestFle:longestFolder)<=25? (longestFolder <= longestFle ? longestFle : longestFolder) : 26;
        int j = 0;

        for (int k = 0; k < folders.Length; k++)
        {
            folders[k] = folders[k].Length <= 25 ? folders[k] : (folders[k].Substring(0, 22) + "...");

            if (folders[k] != directories[i + 1])
            {
                Console.SetCursorPosition(cursorLeft, cursorUp + j);
                Console.WriteLine("+" + folders[k]);
                j++;
            }
            else
            {
                if (i != directories.Length - 2)
                {
                    Console.SetCursorPosition(cursorLeft, cursorUp + j);
                    Console.WriteLine("-" + folders[k] + new string('-', longestName - directories[i + 1].Length) + "--\u261B");
                    j++;
                }
                else
                {
                    Console.ForegroundColor = ConsoleColor.Red;
                    Console.SetCursorPosition(cursorLeft, cursorUp + j);
                    Console.WriteLine("***"+ folders[k] + "***");
                    Console.ForegroundColor = ConsoleColor.Gray;
                    j++;
                }
            }
        }

        for(int k = 0; k <  files.Length; k++)
        {
            files[k] = files[k].Length <= 25 ? files[k] : (files[k].Substring(0, 22) + "...");
            Console.SetCursorPosition(cursorLeft, cursorUp + j);
            Console.WriteLine("+" + files[k]);
            j++;
        }

        cursorUp += Array.IndexOf(folders, directories[i+1]) + 1;
        cursorLeft += longestName+3;
    }
}

Nightjar

Answer 8

Using (y, x) coordinates

C code here:

void printVLine(wchar_t token, unsigned short height, unsigned short y, unsigned short x);
const static wchar_t TREE_VLINE = L'┃';
const static wchar_t TREE_INBRANCH[] = L"┣╾⟶ ";
const static wchar_t TREE_OUTBRANCH[] = L"┗╾⟶ ";

typedef void (*Printer)(void * whateverYouWant);
const static unsigned int  INBRANCH_SIZE = sizeof(TREE_INBRANCH) / sizeof(TREE_INBRANCH[0]);
const static unsigned int OUTBRANCH_SIZE = sizeof(TREE_OUTBRANCH) / sizeof(TREE_OUTBRANCH[0]);

size_t Tree_printFancy(Tree * self, int y, int x, Printer print){
    if (self == NULL) return 0L;
    //
    size_t descendants = y;
    move(y, x);
    print(Tree_at(self));
    if (!Tree_isLeaf(self)){ // in order not to experience unsigned value overflow in while()
        move(++y, x); 
        size_t i = 0;
        while(i < Tree_childrenSize(self) - 1){
            wprintf(TREE_INBRANCH);
            size_t curChildren = Tree_printFancy(
                   Tree_childAt(self, i), y, x + INBRANCH_SIZE, print
            );
            printVLine(TREE_VLINE, curChildren , y + 1, x);
            move((y += curChildren), x);
            ++i;
        }
        wprintf(TREE_OUTBRANCH); 
        y += Tree_printFancy(       // printing outermost child
            Tree_childAt(self, i), y, x + OUTBRANCH_SIZE, print
        ) - 1;
    }   
    return y - descendants + 1;
}

It is applicable rather for console printing. Function move(y, x) moves cursor to (y, x) location on the screen. The best part is, you may change style of output by changing variables TREE_VLINE, TREE_INBRANCH, TREE_OUTBRANCH, length of two last strings doesn't matter. And you can print whatever you like, by passing Printer function pointer, which will print the value of the current tree node. Output looks like this

Venereal