How to print a Binary Tree diagram (vertical) and ensure fairly unbalanced trees are not improperly printed?

I'm trying to write functionality to print a vertical binary tree diagram,

I've got the correct breadth-first search algorithm written, and it outputs the BFS-ordered tree traversal to an integer vector. The code can be seen below:

void bst::printlist(Node* node)
{
    std::queue<Node*> travQueue;
    std::vector<int> result;

    travQueue.push(node);

    while (!travQueue.empty())
    {
        result.push_back(node->val);
        if (node->prev != NULL)
        {
            travQueue.push(node->prev);
        }
        if (node->next != NULL)
        {
            travQueue.push(node->next);
        }
        travQueue.pop();
        node = travQueue.front();
    }
}

However, I am completely stumped on how to convert the resultant vector to one that accurately represents all missing nodes that exist as gaps in a fairly unbalanced tree,

For this example, the vector would only be filled with the integers in the left-to-right order, when it would need to contain information for every missing node all the way down to the bottom level. When going to write the actual code to print the tree with ASCII characters, I will need this information if I am to be able to determine where to and where not to draw nodes -- so, I planned to include dummy values at these gaps to distinguish.

Does anyone have any recommendations for ways to solve this issue?

Thanks!

Solution 1:

Here's a great answer, thanks to @NicoSchertler:

"You can push prev and next to travQueue even if they are nullptr. When you reach a nullptr in your iteration, add the dummy value to the result and two more nullptr to travQueue for the non-existing children."

And here's my code for it:

std::queue<Node*> travQueue;
    std::vector<int> result;

    int h = treeheight(root) + 1;
   
    travQueue.push(node);

    for (int i = 0; i < pow(2, h) - 1; i++)
    {   
        node = travQueue.front();
        if (node != nullptr)
        {
            if (node->prev != nullptr)
            {
                travQueue.push(node->prev);
            } else
            {
                travQueue.push(nullptr);
            }
            if (node->next != nullptr)
            {
                travQueue.push(node->next);
            } else
            {
                travQueue.push(nullptr);
            }
        } else
        {
            travQueue.push(nullptr);
            travQueue.push(nullptr);
        }
        if (node != nullptr)
        {
            result.push_back(node->val);
        } else
        {
            result.push_back(-1);
        }
        travQueue.pop();
    }
    return result;