cdata-structuresqueuebinary-search-treebreadth-first-search

How do I calculate the spaces needed for each line when printing a binary search tree?


I'm trying to make a function that prints a 2d binary search tree in a vertical manner as requested by my professor. However, I'm unable to calculate the proper spacing needed when printing each line of the tree. Which in turn causes it to look messed up.

Here's the loop/segment of my function that prints the current layer:

for (int i = 0; i < nodesInLevel; i++)
        {
            current = dequeue(q);

            if (current != NULL)
            {
                printf("%d", current->data);
                enqueue(q, current->left);
                enqueue(q, current->right);
            }
            else
            {
                printf(" ");
                enqueue(q, NULL);
                enqueue(q, NULL);
            }

            if (i < nodesInLevel - 1) {
                printSpaces(4);
            }
        }
    
        printf("\n");

Simple enough, I'm using breadth traversal to navigate the tree and print each line accordingly. The next part is where the mess is. I'm supposed to print slashes to indicate edges. Which should be easy. Just print a new line, (as seen in the new function) then print slashes according to whether the child exists or not.

The loop in question:

for (int i = 0; i < nodesInNextLevel; i++)
    {
        printSpaces(spaces  -   2);

        if (current == NULL)
        {
            printSpaces(2);
            continue;
        }

        if (current->left == NULL && current->right == NULL)
        {
            continue;
        }
        else if (current->left != NULL && current->right == NULL)
        {
            printSpaces(2);
            putchar('/');
        }
        else if (current->left == NULL && current->right != NULL)
        {
            printSpaces(3);
            putchar('\\');
        }else
        {
            printSpaces(2);
            putchar('/');
            printSpaces(2);
            putchar('\\');
        }
    }
        printf("\n");

both for loops are executed within a bigger for loop with the following variables:

for (int level = 1; level <= treeHeight; level++)
    {
        nodesInLevel = 1 << (level - 1);
        nodesInNextLevel = nodesInLevel;
        spaces = (1 << (treeHeight - level + 1) - 1);
...

Now, it could be because I lack the experience in using binary operators. I did just straight up initialise these variables using chatgpt (an idea I now regret).

But for some reason the output ends up looking like this:

               5
                /  \
        3    45
        /  \        /  \
    2    4    25    105

as opposed to what I want, which is:

             5
            /  \
           3     45
         /  \   /  \
        2   4  25 105

How do I correct my calculations, and how do I even do such calculations moving forward when thinking up/ drafting the concept of the program.

Not sure if this counts as an MCVE: But here's the link to my code where all my functions, structs and header file are stored. https://gist.github.com/SalManRAMc/fa636355cc042df3868b630e19ba8c97


Solution

  • You didn't post a compilable code, hence there is the raw roadmap.

    If the tree is balanced, take the max digits in nodes of the leaves, say D.

    The length of the line placeholder is (D + 1) * N, let say L, where N is 2^(tree depth + 1).

    For each line output like (L - N * (level node count)) / 2 spaces followed by nodes split by (depth - level) spaces.

    You will get

          5
      3      45
    2   4  25 105
    

    When you get it implemented and debugged, move forward: add even lines similarly to that + 1 line, but node values are just alternative / and \ .

    Summarize: the node values max length is D, each node takes D + 1 (value + margins + space separator), the left first line alignment is last line length / 2 minus the node size, each next left line alignment is /2 of prev one, similar space between nodes is counted accordantly. You can see some math here printTree(), the math here can help although it's C++.