How to print a 2D visual of a BST from root to leaves?

[vaderboi]

I am having a hard time knowing how to print a 2D visual of a binary search tree from root to leaves because I don't how to accomplish this and have the tree print in the correct order. For example, I would like the output to look something like this (and yes, I know this would need to be balanced; I don't need help with that):

                         5
                        / \
                       4   6
                      /     \
                     2       9
                    / \     / \
                   0   3   7   10
                    \            \
                     1           13                    

Does anyone have any tips to accomplish this visual? Would I use recursion? I have been looking up ways to do this and have been having a hard time finding anything relevant.

[dutch]

How would you draw a full tree of four levels like that?

[vaderboi]

I would start at the top and then go down.

[dutch]

ok

[vaderboi]

Oh I didn't mean that your method was worse than mine. I thought you were asking how I thought it should be approached. You are right that doing it from the top would be very difficult to implement and that doing it horizontally probably makes more sense.

[lastchance]

You may need to play with the spacing a bit. It's rather wonky. Dunno how well it works for larger trees. (EDIT: not very well; back to the drawing board).

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

//==========================================================

class Tree
{
private:          
   struct Node
   {
      int data;
      Node* left  = nullptr;
      Node* right = nullptr;

      Node( int val ) : data( val ) {}
   };

   Node* root = nullptr;
   Node* insert( Node*, int );
   void  print ( Node* );

public:
   void insert( int val ) { root = insert( root, val ); }
   void print() { print( root ); cout << '\n'; }

   // For drawing
private:
   int height( Node* );
   void drawNode( vector<string> &output, vector<string> &linkAbove, Node* node, int level, int minPos, char linkChar );
public:
   void draw();
};

//----------------------------

Tree::Node* Tree::insert( Node* node, int val )
{
   if ( !node ) return new Node( val );
   if ( val < node->data ) node->left  = insert( node->left, val );
   else                    node->right = insert( node->right, val );
   return node;
}

//----------------------------

void Tree::print( Node* node )
{
   if ( !node ) return;
   print( node->left  );
   cout << node->data << " ";
   print( node->right );
}

//==========================================================

int Tree::height( Node* node )
{
   if ( !node ) return 0;
   return 1 + max( height( node->left ), height( node->right ) );
}

//----------------------------

void Tree::drawNode( vector<string> &output, vector<string> &linkAbove, Node* node, int level, int p, char linkChar )
{
   if ( !node ) return;
   
   p = max( p, 0 );

   // Fill in everything to left
   if ( node->left ) 
   {
      drawNode( output, linkAbove, node->left, level + 1, p - to_string( node->left->data ).size() - 2, '/' );
      p = max( p, (int)output[level+1].size() );
   }

   // Enter this data
   int space = p - output[level].size();
   if ( space > 0 ) output[level] += string( space, ' ' );
   output[level] += ' ' + to_string( node->data ) + ' ';

   if ( linkChar == '/' ) p = output[level].size() - 1;
   space = p - linkAbove[level].size();
   if ( space > 0 ) linkAbove[level] += string( space, ' ' );
   linkAbove[level] += linkChar;


   // Fill in everything to right
   p = output[level].size();
   drawNode( output, linkAbove, node->right, level + 1, p, '\\' );
}

//----------------------------

void Tree::draw()
{
   int h = height( root );
   vector<string> output( h ), linkAbove( h );
   drawNode( output, linkAbove, root, 0, 0, ' ' );

   for ( int i = 0; i < h; i++ )
   {  
      if ( i ) cout << linkAbove[i] << '\n';
      cout << output[i] << '\n';
   }
}


//==========================================================

int main()
{
   int A[] = { 5, 4, 6, 2, 9, 0, 3, 7, 10, 1, 13 };

   Tree tree;
   for ( int i : A ) tree.insert( i );
// tree.print();
   tree.draw();
}

[dutch]

That's pretty good.
All your private functions should be static, though.

[lastchance]

Slightly more reliable version.

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;

//==================

class Tree
{
private:          
   struct Node
   {
      int data;
      Node* left  = nullptr;
      Node* right = nullptr;

      Node( int val ) : data( val ) {}
   };

   Node* root = nullptr;
   Node* insert( Node*, int );
   void  print ( Node* );

public:
   void insert( int val ) { root = insert( root, val ); }
   void print() { print( root ); cout << '\n'; }

   // For drawing
private:
   int height( Node* );
   void drawNode( vector<string> &output, vector<string> &linkAbove, Node* node, int level, int minPos, char linkChar );
public:
   void draw();
};

//------------------

Tree::Node* Tree::insert( Node* node, int val )
{
   if ( !node ) return new Node( val );
   if ( val < node->data ) node->left  = insert( node->left, val );
   else                    node->right = insert( node->right, val );   // ...
// if ( val > node->data ) node->right = insert( node->right, val );   // alternative with no repeats
   return node;
}

//------------------

void Tree::print( Node* node )
{
   if ( !node ) return;
   print( node->left  );
   cout << node->data << " ";
   print( node->right );
}

//==================

int Tree::height( Node* node )
{
   if ( !node ) return 0;
   return 1 + max( height( node->left ), height( node->right ) );
}

//------------------

void Tree::drawNode( vector<string> &output, vector<string> &linkAbove, Node* node, int level, int p, char linkChar )
{
   if ( !node ) return;

   int h = output.size();
   string SP = " ";
   
   if ( p < 0 )       // Shunt everything non-blank across
   {
      string extra( -p, ' ' );
      for ( string &s : output    ) if ( !s.empty() ) s = extra + s;
      for ( string &s : linkAbove ) if ( !s.empty() ) s = extra + s;
   }
   if ( level < h - 1 ) p = max( p, (int)output[level+1].size() );
   if ( level > 0     ) p = max( p, (int)output[level-1].size() );
   p = max( p, (int)output[level].size() );
   
   // Fill in to left
   if ( node->left ) 
   {
      string leftData = SP + to_string( node->left->data ) + SP;
      drawNode( output, linkAbove, node->left, level + 1, p - leftData.size(), 'L' );
      p = max( p, (int)output[level+1].size() );
   }

   // Enter this data
   int space = p - output[level].size();  if ( space > 0 ) output[level] += string( space, ' ' );
   string nodeData = SP + to_string( node->data ) + SP;
   output[level] += nodeData;

   // Add vertical link above
   space = p + SP.size() - linkAbove[level].size();   if ( space > 0 ) linkAbove[level] += string( space, ' ' );
   linkAbove[level] += linkChar;

   // Fill in to right
   if ( node->right ) drawNode( output, linkAbove, node->right, level + 1, output[level].size(), 'R' );
}

//------------------

void Tree::draw()
{
   int h = height( root );
   vector<string> output( h ), linkAbove( h );
   drawNode( output, linkAbove, root, 0, 5, ' ' );

   // Create link lines
   for ( int i = 1; i < h; i++ )
   {
      for ( int j = 0; j < linkAbove[i].size(); j++ )
      {
         if ( linkAbove[i][j] != ' ' )
         {
            int size = output[i-1].size();
            if ( size < j + 1 ) output[i-1] += string( j + 1 - size, ' ' );
            int jj = j;
            if ( linkAbove[i][j] == 'L' )
            {
               while ( output[i-1][jj] == ' ' ) jj++;
               for ( int k = j + 1; k < jj - 1; k++ ) output[i-1][k] = '_';
            }
            else if ( linkAbove[i][j] == 'R' )
            {
               while ( output[i-1][jj] == ' ' ) jj--;
               for ( int k = j - 1; k > jj + 1; k-- ) output[i-1][k] = '_';
            }
            linkAbove[i][j] = '|';
         }
      }
   }

   // Output
   for ( int i = 0; i < h; i++ )
   {  
      if ( i ) cout << linkAbove[i] << '\n';
      cout << output[i] << '\n';
   }
}

//==================

int main()
{
   srand( time( 0 ) );
// vector<int> A = { 5, 4, 6, 2, 9, 0, 3, 7, 10, 1, 13 };                        // Test input
   vector<int> A;   for ( int i = 0; i < 50; i++ ) A.push_back( rand() % 100 );  // Bigger tree

   Tree tree;
   for ( int i : A ) tree.insert( i );
// tree.print();
   tree.draw();
}

       _ 5 _ 
      |     |
    _ 4     6 _ 
   |           |
 _ 2 _       _ 9 _ 
|     |     |     |
0 _   3     7     10 _ 
   |                  |
   1                  13 

    _ 12 ________________ 
   |                     |
 _ 3 _______          __ 88 _________________________________________ 
|           |        |                                               |
0 _       _ 9     __ 22 _________________________                 __ 96 _________________ 
   |     |       |                               |               |                       |
   0   _ 8    __ 21 _                         __ 59 _________    88 _________         __ 99 
      |      |       |                       |               |               |       |
      7   __ 16 _    21                   __ 51 _         __ 75 _________    88 _    96 _ 
         |       |                       |       |       |               |       |       |
      __ 13      16 _                 __ 32 _    54   __ 74           __ 84   __ 92 _    96 
     |               |               |       |       |               |       |       |
     12           __ 19 _         __ 31   __ 40 _    64 _____     __ 83      89 _    92 
                 |       |       |       |       |           |   |               |
                 17      20   __ 26      37   __ 44 _     __ 70  81              90 
                             |               |       |   |
                             22           __ 41      44  65 _ 
                                         |                   |
                                         40                  68 

No repeats:

               __ 74 ___________________________________________ 
              |                                                 |
           __ 58 _                                           __ 86 _________ 
          |       |                                         |               |
       __ 11 _    59 ___________________________         __ 78 _____     __ 91 _ 
      |       |                                 |       |           |   |       |
    _ 10   __ 37 ___________                 __ 72 _    76 _     __ 85  88      98 
   |      |                 |               |       |       |   |
 _ 2 _    13 ___         __ 50 _         __ 67 _    73      77  83 
|     |         |       |       |       |       |
0     4 _    __ 19 _    47      54   __ 66      70 
         |  |       |               |
         6  18      20 _            60 _ 
                        |               |
                     __ 36              63 
                    |
                    26 _ 
                        |
                     __ 35 
                    |
                 __ 31 
                |
                30