How to display binary search tree in console properly?

Question

I'm trying to display a BST in console. That's my code (it's a modified version of code found here: Printing Level Order Binary Search Tree Formatting):

string printLevel(node *root, int level, string gap) {
  if (!root) {
    return gap + "-" + gap;
  }
  if (level==1) {
    stringstream out;
    out<<root->value;
    return gap + out.str() + gap;
  } else if (level>1) {
    string leftStr = printLevel(root->left, level-1, gap);
    string rightStr = printLevel(root->right, level-1, gap);
    return leftStr + " " + rightStr;
  } else return "";
}

void printLevelOrder (node* root, int depth) {
  for (int i=1; i<=depth; i++) {
    string gap="";
    for (int j=0; j<pow(2,depth-i)-1; j++) {
      gap+=" ";
    }
    string levelNodes = printLevel(root, i, gap);
    cout<<levelNodes<<endl;
  }
}

For example result should be like that:

       4
   1       6
 -   2   5   - 
- - - 3 - - - -

But instead it is:

       4       
   1       6
 -   2   5   -
- - 3 - - -

If I undestand correctly, the recursion stops when the program makes it to the empty leaf and therefore there are lacking " - " on the lower levels in the result. But how do I know how much of those I should draw on the lower levels? How to make this work?

You also have an issue with where 3 is displayed, it should be to the right of 2. — Matthieu M.
– Matthieu M., Commented Apr 6, 2013 at 17:04
@MatthieuM. That's actually bound to the main issue. If the tree was displayed correctly, the 3 would have been on its place. In the means of data structure, it is a right child of the 2. — raven_raven
– raven_raven, Commented Apr 6, 2013 at 17:13

Matthieu M. · Accepted Answer · 2013-04-06 17:56:16Z

I instrumented the code to see where it went awry (since running a debugger in a browser...), you can see it live here. The reproduced function is:

string printLevel(node *root, int level, string gap) {
  if (root == 0) {
    cout << ".. printLevel - " << root << ": " << gap << "-" << gap << "\n";
    return gap + "-" + gap;
  }
  if (level==1) {
    stringstream out;
    out<<root->value;
    cout << ".. printLevel - " << root << ": " << gap << root->value << gap << "\n";
    return gap + out.str() + gap;
  } else if (level>1) {
    string leftStr = printLevel(root->left, level-1, gap);
    string rightStr = printLevel(root->right, level-1, gap);

    cout << ".. printLevel - " << root << ": '" << leftStr << "', '" << rightStr << "'\n";
    return leftStr + " " + rightStr;
  } else return "";
}

And here is the bit of interesting output:

.. printLevel - <none>: -
.. printLevel - <none>: -
.. printLevel - { 3, <none>, <none> }: 3
.. printLevel - { 2, <none>, { 3, <none>, <none> } }: '-', '3'
.. printLevel - { 1, <none>, { 2, <none>, { 3, <none>, <none> } } }: '-', '- 3'

So, the issue is that you short-circuit whenever root is 0, which is actually an issue: - is not the right output unless level is 1.

The only difference between root being 0 and root not being 0 is that you cannot read the value out of it (and thus get to replace it by -); however you only really read that value when level is 1 (beware, you might try to read left or right too), therefore there is no reason to test for root == 0 unless you are in the level == 1 branch.

Let us slightly reorder things then:

string printLevel(node *root, int level, string gap) {
  if (level==1) {
//    if (root == 0) {
//      cout << ".. printLevel - " << root << ": " << gap << "-" << gap << "\n";
//      return gap + "-" + gap;
//    }
    stringstream out;
    out<<root->value;
    cout << ".. printLevel - " << root << ": " << gap << root->value << gap << "\n";
    return gap + out.str() + gap;
  } else if (level>1) {
//    string leftStr = printLevel(root ? root->left : 0, level-1, gap);
//    string rightStr = printLevel(root ? root->right : 0, level-1, gap);

    cout << ".. printLevel - " << root << ": '" << leftStr << "', '" << rightStr << "'\n";
    return leftStr + " " + rightStr;
  } else return "";
}

Note: I "highlighted" the modified lines with "comments".

And now, the tree prints properly.

Now it's working perfectly! Thank you so much for tips and code! Such elegant solution, also thank you for sharing this liveworkspace link, taught me few tricks.
@raven_raven: liveworkspace (and other online compilers) is a good solution for quick and dirty experiment since we don't have a REPL in C++... and sharing it is so easy!

RedFox · Accepted Answer · 2014-02-15 05:40:55Z

2

void BinaryTree::Display(TreeNode *current, int indent)
{
    if (current != nullptr)
    {
        Display(current->left, indent + 4);
        if (indent > 0)
            cout << setw(indent) << " ";
        cout << current->value << endl;
        Display(current->right, indent + 4);
    }
}

prints tree left to right instead of top down.

answered Feb 15, 2014 at 5:40

RedFox

1,4163 gold badges18 silver badges31 bronze badges

Comments

almighty Push · Accepted Answer · 2017-08-01 05:28:49Z

Here is my code. It prints very well,maybe its not perfectly symmetrical. little description:

1st function - prints level by level (root lv -> leaves lv)
2nd function - distance from the beginning of new line
3rd function - prints nodes and calculates distance between two prints;

void Tree::TREEPRINT()
{
    int i = 0;
    while (i <= treeHeight(getroot())){
        printlv(i);
        i++;
        cout << endl;
    }
}

void Tree::printlv(int n){
    Node* temp = getroot();
    int val = pow(2, treeHeight(root) -n+2);
    cout << setw(val) << "";
    prinlv(temp, n, val);
}

void Tree::dispLV(Node*p, int lv, int d)
{
    int disp = 2 * d;
    if (lv == 0){
        if (p == NULL){

            cout << " x ";
            cout << setw(disp -3) << "";
            return;
        }
        else{
            int result = ((p->key <= 1) ? 1 : log10(p->key) + 1);
            cout << " " << p->key << " ";
            cout << setw(disp - result-2) << "";
        }
    }
    else
    {
        if (p == NULL&& lv >= 1){
            dispLV(NULL, lv - 1, d);
            dispLV(NULL, lv - 1, d);
        }
        else{
            dispLV(p->left, lv - 1, d);
            dispLV(p->right, lv - 1, d);
        }
    }
}

Input:

50-28-19-30-29-17-42-200-160-170-180-240-44-26-27

Output: https://i.sstatic.net/TtPXY.png

Collectives™ on Stack Overflow

How to display binary search tree in console properly?

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related