1

I have the following code for a Binary Search Tree:

#include <iostream>
#include <iomanip>

using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) {
        data = val;
        left = nullptr;
        right = nullptr;
    }
};

void insert(Node*& root, int val) {
    if (root == nullptr) {
        root = new Node(val);
        return;
    }
    if (val < root->data) {
        insert(root->left, val);
    }
    else {
        insert(root->right, val);
    }
}

void printTree(Node* root, int indent=0) {
    if (root) {
        printTree(root->right, indent+0);
        if (indent) {
            std::cout << std::setw(indent) << ' ';
        }
        if (root->right) {
            std::cout << "/ \n";
        }
        std::cout << root->data << '\n';
        if (root->left) {
            std::cout << std::setw(indent) << ' ' << " \\\n";
        }
        printTree(root->left, indent+2);
    }
}

int main() {
    Node* root = nullptr;
    insert(root, 9);
    insert(root, 8);
    insert(root, 7);
    insert(root, 6);
    insert(root, 5);
    insert(root, 4);
    insert(root, 3);
    insert(root, 5);

    printTree(root, 0);

    return 0;
}

This is the output I'm getting:

9
  \
  8
   \
    7
     \
      6
       \
        5
        / 
5
         \
          4
           \
            3

Looks almost good. Just need that left most 5 to align under its parent root 5 directly. Messed around with the indentation a bit but unable to get it to work without messing up the other nodes.

What should I do to finally get the alignment right?

Expected:

9
  \
  8
   \
    7
     \
      6
       \
        5
       / \
      5   4
           \
            3

Tried a different way:

void printTree(Node* root, int level) {
    if (root == nullptr) {
        return;
    }
    printTree(root->right, level + 1);
    for (int i = 0; i < level; i++) {
        std::cout << "  ";
    }
    if (root->left != nullptr && root->right != nullptr) {
        std::cout << root->data << "/ \\" << std::endl;
    }
    else if (root->right != nullptr) {
        std::cout << root->data << " /" << std::endl;
    }
    else if (root->left != nullptr) {
        std::cout << root->data << "\\ " << std::endl;
    }
    else {
        std::cout << root->data << std::endl;
    }
    printTree(root->left, level + 1);
}

It's right, however, the display isnt as great as the method above with indentation/setw() combo (I want the slashes to represent branches on a new line not next to the node itself)

9\ 
  8\ 
    7\ 
      6\ 
          5
        5/ \
          4\ 
            3
Cataster
  • 3,081
  • 5
  • 32
  • 79
  • Your desired output shows the `4` node connected to the second `5` node which is not correct. It should be under the first `5` node. So I think your problems are greater than just some wonky indenting. I would experiment with some smaller and shallower trees. I think you are underestimating how difficult printing a tree is. Nodes at similar depths should be printed on the same line, your code never does that. – john Mar 02 '23 at 07:00
  • As you can see here `std::cout << root->data << '\n';` your code will always print each node on a separate line. – john Mar 02 '23 at 07:01
  • @john ah! thats true, the 4 subtree should be under the 1st 5 subtree. hmm, whats going on... – Cataster Mar 02 '23 at 07:03
  • @john tried a different way but the branches are next to the node. If there is a way to make it look like desired output that would be perfect. check my edited post – Cataster Mar 02 '23 at 07:16
  • A *search* tree does not normally contain duplicate keys. – molbdnilo Mar 02 '23 at 07:25
  • 1
    What you are trying to do is much more complicated than your current attempt. What if the bottom "5" has an entire subtree below it? – nielsen Mar 02 '23 at 07:36
  • If your tree has 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15, inserted in this order, what output do you want to get? – n. m. could be an AI Mar 02 '23 at 07:48

0 Answers0