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

vaderboi (140)
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):

1
2
3
4
5
6
7
8
9
10
 
                         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.
Last edited on
dutch (2548)
How would you draw a full tree of four levels like that?
Last edited on
vaderboi (140)
I would start at the top and then go down.
dutch (2548)
ok
vaderboi (140)
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 (6980)
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).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
#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();
}

Last edited on
dutch (2548)
That's pretty good.
All your private functions should be static, though.
lastchance (6980)
Slightly more reliable version.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
#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
Last edited on
Topic archived. No new replies allowed.