C# Display a Binary Search Tree in Console

Question

I have simple binary search tree

public class BNode
{
    public int item;
    public BNode right;
    public BNode left;

    public BNode(int item)
    {
        this.item = item;
    }
}

public class BTree
{
    private BNode _root;
    private int _count;
    private IComparer<int> _comparer = Comparer<int>.Default;


    public BTree()
    {
        _root = null;
        _count = 0;
    }


    public bool Add(int Item)
    {
        if (_root == null)
        {
            _root = new BNode(Item);
            _count++;
            return true;
        }
        else
        {
            return Add_Sub(_root, Item);
        }
    }

    private bool Add_Sub(BNode Node, int Item)
    {
        if (_comparer.Compare(Node.item, Item) < 0)
        {
            if (Node.right == null)
            {
                Node.right = new BNode(Item);
                _count++;
                return true;
            }
            else
            {
                return Add_Sub(Node.right, Item);
            }
        }
        else if (_comparer.Compare(Node.item, Item) > 0)
        {
            if (Node.left == null)
            {
                Node.left = new BNode(Item);
                _count++;
                return true;
            }
            else
            {
                return Add_Sub(Node.left, Item);
            }
        }
        else
        {
            return false;
        }
    }

    public void Print()
    {
        Print(_root, 4);
    }

    public void Print(BNode p, int padding)
    {
        if (p != null)
        {
            if (p.right != null)
            {
                Print(p.right, padding + 4);
            }
            if (padding > 0)
            {
                Console.Write(" ".PadLeft(padding));
            }
            if (p.right != null)
            {
                Console.Write("/\n");
                Console.Write(" ".PadLeft(padding));
            }
            Console.Write(p.item.ToString() + "\n ");
            if (p.left != null)
            {
                Console.Write(" ".PadLeft(padding) + "\\\n");
                Print(p.left, padding + 4);
            }
        }
    }
}

where I can insert values like

BTree btr = new BTree();
btr.Add(6);
btr.Add(2);
btr.Add(3);
btr.Add(11);
btr.Add(30);
btr.Add(9);
btr.Add(13);
btr.Add(18);

I want to display my tree within my console application. I have a btr.Print(); which displays my tree from left to right (6 is the root) - but I'm not happy with it.

Question: Is there a better way to display this tree within a console application? Even a improvement of this Print() would help me.

I think the approach in this other link looks nicer and more compact: http://stackoverflow.com/a/1649223/831138 . "Compact" in the sense that one can fit more information in the same screen space... of course it is going to stretch it vertically, but using the scrollbar of the console shouldn't be a problem... running out of horizontal space is a problem. — Xavier Peña, Mar 30 '16 at 15:12
Possible duplicate of [Tree visualization algorithm](http://stackoverflow.com/questions/8368386/tree-visualization-algorithm) — mbeckish, Mar 30 '16 at 16:38
http://stackoverflow.com/questions/801740/c-how-to-draw-a-binary-tree-to-the-console — fubo, Apr 11 '16 at 06:07

Ivan Stoev · Accepted Answer · 2016-04-10T15:20:32.900

I've ended up with the following method that allows you to print arbitrary subtree:

public static class BTreePrinter
{
    class NodeInfo
    {
        public BNode Node;
        public string Text;
        public int StartPos;
        public int Size { get { return Text.Length; } }
        public int EndPos { get { return StartPos + Size; } set { StartPos = value - Size; } }
        public NodeInfo Parent, Left, Right;
    }

    public static void Print(this BNode root, string textFormat = "0", int spacing = 1, int topMargin = 2, int leftMargin = 2)
    {
        if (root == null) return;
        int rootTop = Console.CursorTop + topMargin;
        var last = new List<NodeInfo>();
        var next = root;
        for (int level = 0; next != null; level++)
        {
            var item = new NodeInfo { Node = next, Text = next.item.ToString(textFormat) };
            if (level < last.Count)
            {
                item.StartPos = last[level].EndPos + spacing;
                last[level] = item;
            }
            else
            {
                item.StartPos = leftMargin;
                last.Add(item);
            }
            if (level > 0)
            {
                item.Parent = last[level - 1];
                if (next == item.Parent.Node.left)
                {
                    item.Parent.Left = item;
                    item.EndPos = Math.Max(item.EndPos, item.Parent.StartPos - 1);
                }
                else
                {
                    item.Parent.Right = item;
                    item.StartPos = Math.Max(item.StartPos, item.Parent.EndPos + 1);
                }
            }
            next = next.left ?? next.right;
            for (; next == null; item = item.Parent)
            {
                int top = rootTop + 2 * level;
                Print(item.Text, top, item.StartPos);
                if (item.Left != null)
                {
                    Print("/", top + 1, item.Left.EndPos);
                    Print("_", top, item.Left.EndPos + 1, item.StartPos);
                }
                if (item.Right != null)
                {
                    Print("_", top, item.EndPos, item.Right.StartPos - 1);
                    Print("\\", top + 1, item.Right.StartPos - 1);
                }
                if (--level < 0) break;
                if (item == item.Parent.Left)
                {
                    item.Parent.StartPos = item.EndPos + 1;
                    next = item.Parent.Node.right;
                }
                else
                {
                    if (item.Parent.Left == null)
                        item.Parent.EndPos = item.StartPos - 1;
                    else
                        item.Parent.StartPos += (item.StartPos - 1 - item.Parent.EndPos) / 2;
                }
            }
        }
        Console.SetCursorPosition(0, rootTop + 2 * last.Count - 1);
    }

    private static void Print(string s, int top, int left, int right = -1)
    {
        Console.SetCursorPosition(left, top);
        if (right < 0) right = left + s.Length;
        while (Console.CursorLeft < right) Console.Write(s);
    }
}

As you can see, I've added some parameters that affect the formatting. By default it produces the most compact representation.

In order to play with it, I've modified the BTree class as follows:

public class BTree
{
    // ...

    public BNode Root { get { return _root; } }

    public void Print()
    {
        Root.Print();
    }
}

Using your sample data, here are some results:

btr.Root.Print();

btr.Root.Print(textFormat: "(0)", spacing: 2);

UPDATE: IMO the default format above is compact and readable, but just for fun, adjusted the algorithm to produce more "graphical" output (textFormat and spacing parameters removed):

public static class BTreePrinter
{
    class NodeInfo
    {
        public BNode Node;
        public string Text;
        public int StartPos;
        public int Size { get { return Text.Length; } }
        public int EndPos { get { return StartPos + Size; } set { StartPos = value - Size; } }
        public NodeInfo Parent, Left, Right;
    }

    public static void Print(this BNode root, int topMargin = 2, int leftMargin = 2)
    {
        if (root == null) return;
        int rootTop = Console.CursorTop + topMargin;
        var last = new List<NodeInfo>();
        var next = root;
        for (int level = 0; next != null; level++)
        {
            var item = new NodeInfo { Node = next, Text = next.item.ToString(" 0 ") };
            if (level < last.Count)
            {
                item.StartPos = last[level].EndPos + 1;
                last[level] = item;
            }
            else
            {
                item.StartPos = leftMargin;
                last.Add(item);
            }
            if (level > 0)
            {
                item.Parent = last[level - 1];
                if (next == item.Parent.Node.left)
                {
                    item.Parent.Left = item;
                    item.EndPos = Math.Max(item.EndPos, item.Parent.StartPos);
                }
                else
                {
                    item.Parent.Right = item;
                    item.StartPos = Math.Max(item.StartPos, item.Parent.EndPos);
                }
            }
            next = next.left ?? next.right;
            for (; next == null; item = item.Parent)
            {
                Print(item, rootTop + 2 * level);
                if (--level < 0) break;
                if (item == item.Parent.Left)
                {
                    item.Parent.StartPos = item.EndPos;
                    next = item.Parent.Node.right;
                }
                else
                {
                    if (item.Parent.Left == null)
                        item.Parent.EndPos = item.StartPos;
                    else
                        item.Parent.StartPos += (item.StartPos - item.Parent.EndPos) / 2;
                }
            }
        }
        Console.SetCursorPosition(0, rootTop + 2 * last.Count - 1);
    }

    private static void Print(NodeInfo item, int top)
    {
        SwapColors();
        Print(item.Text, top, item.StartPos);
        SwapColors();
        if (item.Left != null)
            PrintLink(top + 1, "┌", "┘", item.Left.StartPos + item.Left.Size / 2, item.StartPos);
        if (item.Right != null)
            PrintLink(top + 1, "└", "┐", item.EndPos - 1, item.Right.StartPos + item.Right.Size / 2);
    }

    private static void PrintLink(int top, string start, string end, int startPos, int endPos)
    {
        Print(start, top, startPos);
        Print("─", top, startPos + 1, endPos);
        Print(end, top, endPos);
    }

    private static void Print(string s, int top, int left, int right = -1)
    {
        Console.SetCursorPosition(left, top);
        if (right < 0) right = left + s.Length;
        while (Console.CursorLeft < right) Console.Write(s);
    }

    private static void SwapColors()
    {
        var color = Console.ForegroundColor;
        Console.ForegroundColor = Console.BackgroundColor;
        Console.BackgroundColor = color;
    }
}

and the result is:

Xavier Peña · Answer 2 · 2016-03-31T10:54:56.757

This is my take at it:

I've added PrintPretty to BNode, and I've removed the second Print function you had in BTree.

(Edit: I made the tree more lisible by changing the original chars to draw the branches of the tree)

    static void Main(string[] args)
    {
        BTree btr = new BTree();
        btr.Add(6);
        btr.Add(2);
        btr.Add(3);
        btr.Add(11);
        btr.Add(30);
        btr.Add(9);
        btr.Add(13);
        btr.Add(18);

        btr.Print();

    }

    public class BNode
    {
        public int item;
        public BNode right;
        public BNode left;

        public BNode(int item)
        {
            this.item = item;
        }

        public void PrintPretty(string indent, bool last)
        {

            Console.Write(indent);
            if (last)
            {
                Console.Write("└─");
                indent += "  ";
            }
            else
            {
                Console.Write("├─");
                indent += "| ";
            }
            Console.WriteLine(item);

            var children = new List<BNode>();
            if (this.left != null)
                children.Add(this.left);
            if (this.right != null)
                children.Add(this.right);

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

        }

    }

    public class BTree
    {
        private BNode _root;
        private int _count;
        private IComparer<int> _comparer = Comparer<int>.Default;


        public BTree()
        {
            _root = null;
            _count = 0;
        }


        public bool Add(int Item)
        {
            if (_root == null)
            {
                _root = new BNode(Item);
                _count++;
                return true;
            }
            else
            {
                return Add_Sub(_root, Item);
            }
        }

        private bool Add_Sub(BNode Node, int Item)
        {
            if (_comparer.Compare(Node.item, Item) < 0)
            {
                if (Node.right == null)
                {
                    Node.right = new BNode(Item);
                    _count++;
                    return true;
                }
                else
                {
                    return Add_Sub(Node.right, Item);
                }
            }
            else if (_comparer.Compare(Node.item, Item) > 0)
            {
                if (Node.left == null)
                {
                    Node.left = new BNode(Item);
                    _count++;
                    return true;
                }
                else
                {
                    return Add_Sub(Node.left, Item);
                }
            }
            else
            {
                return false;
            }
        }

        public void Print()
        {
            _root.PrintPretty("", true);
        }

    }

This is the result (more compact, as I mentioned):

Edit: the following code has been modified in order to show the info about left-right:

    static void Main(string[] args)
    {
        BTree btr = new BTree();
        btr.Add(6);
        btr.Add(2);
        btr.Add(3);
        btr.Add(11);
        btr.Add(30);
        btr.Add(9);
        btr.Add(13);
        btr.Add(18);

        btr.Print();

    }

    public enum NodePosition
    {
        left,
        right,
        center
    }

    public class BNode
    {
        public int item;
        public BNode right;
        public BNode left;

        public BNode(int item)
        {
            this.item = item;
        }

        private void PrintValue(string value, NodePosition nodePostion)
        {
            switch (nodePostion)
            {
                case NodePosition.left:
                    PrintLeftValue(value);
                    break;
                case NodePosition.right:
                    PrintRightValue(value);
                    break;
                case NodePosition.center:
                    Console.WriteLine(value);
                    break;
                default:
                    throw new NotImplementedException();
            }
        }

        private void PrintLeftValue(string value)
        {
            Console.ForegroundColor = ConsoleColor.Magenta;
            Console.Write("L:");
            Console.ForegroundColor = (value == "-") ? ConsoleColor.Red : ConsoleColor.Gray;
            Console.WriteLine(value);
            Console.ForegroundColor = ConsoleColor.Gray;
        }

        private void PrintRightValue(string value)
        {
            Console.ForegroundColor = ConsoleColor.Green;
            Console.Write("R:");
            Console.ForegroundColor = (value == "-") ? ConsoleColor.Red : ConsoleColor.Gray;
            Console.WriteLine(value);
            Console.ForegroundColor = ConsoleColor.Gray;
        }

        public void PrintPretty(string indent, NodePosition nodePosition, bool last, bool empty)
        {

            Console.Write(indent);
            if (last)
            {
                Console.Write("└─");
                indent += "  ";
            }
            else
            {
                Console.Write("├─");
                indent += "| ";
            }

            var stringValue = empty ? "-" : item.ToString();
            PrintValue(stringValue, nodePosition);

            if(!empty && (this.left != null || this.right != null))
            {
                if (this.left != null)
                    this.left.PrintPretty(indent, NodePosition.left, false, false);
                else
                    PrintPretty(indent, NodePosition.left, false, true);

                if (this.right != null)
                    this.right.PrintPretty(indent, NodePosition.right, true, false);
                else
                    PrintPretty(indent, NodePosition.right, true, true);
            }
        }

    }

    public class BTree
    {
        private BNode _root;
        private int _count;
        private IComparer<int> _comparer = Comparer<int>.Default;


        public BTree()
        {
            _root = null;
            _count = 0;
        }


        public bool Add(int Item)
        {
            if (_root == null)
            {
                _root = new BNode(Item);
                _count++;
                return true;
            }
            else
            {
                return Add_Sub(_root, Item);
            }
        }

        private bool Add_Sub(BNode Node, int Item)
        {
            if (_comparer.Compare(Node.item, Item) < 0)
            {
                if (Node.right == null)
                {
                    Node.right = new BNode(Item);
                    _count++;
                    return true;
                }
                else
                {
                    return Add_Sub(Node.right, Item);
                }
            }
            else if (_comparer.Compare(Node.item, Item) > 0)
            {
                if (Node.left == null)
                {
                    Node.left = new BNode(Item);
                    _count++;
                    return true;
                }
                else
                {
                    return Add_Sub(Node.left, Item);
                }
            }
            else
            {
                return false;
            }
        }

        public void Print()
        {
            _root.PrintPretty("", NodePosition.center, true, false);
        }

    }

The result:

ok this is defiantly a improved and more compact version +1 - but it loses one information - if a child node is on the left side (value is lower than the parent node) or on the right side (value is higher) — fubo, Mar 31 '16 at 05:52
@fubo You are absolutely right, I thought about it yesterday after posting it but I had no time to correct it... Now I have changed the code a little to show the info about left and right. One thing that one can use in a console in order add more visual info is to play with the colors, and this is also something that I've added to this new version. — Xavier Peña, Mar 31 '16 at 10:58

halllo · Answer 3 · 2021-01-06T12:47:55.027

If your tree is in the form of a QuickGraph IBidirectionalGraph, you could print it recursively like this:

static void PrintVertex<TVertex>(IBidirectionalGraph<TVertex, IEdge<TVertex>> graph, TVertex vertex, Func<TVertex, string> labelSelector, bool[] isLastVertexIntendations = null)
{
    var prefix = string.Concat(Enumerable.Concat(
        /*up to last*/isLastVertexIntendations.NeverNull().Reverse().Skip(1).Reverse().Select(isLast => isLast ? "  " : "│ "),
        /*last*/isLastVertexIntendations.NeverNull().Reverse().Take(1).Select(isLast => isLast ? "└─" : "├─")
    ));
    Console.Write(prefix);
    Console.WriteLine(labelSelector(vertex));
    var edges = graph.OutEdges(vertex);
    foreach (var edge in edges)
    {
        PrintVertex(graph, edge.Target, labelSelector, isLastVertexIntendations: isLastVertexIntendations.NeverNull().Concat(new[] { edge == edges.Last() }).ToArray());
    }
}

C# Display a Binary Search Tree in Console

3 Answers3

Linked