@gabryon | visualizing-binary-tree

Visualizing Binary Tree

3 min. read 5 August 2022

The Story

Hello people! This is my first article on my personal blog, I've waited for so long before writing something. Usually, I don't have things to say but, I hope this experience may help someone.

Many developers, when debugging programs, place some random print statement (instead of using a debugging tool such as gdb, lldb, but, anyway...). This simplistic approach (or the serious one) does not help in visualizing graph-like data structures, like Binary Search Tree!
I had to debug my implementation of Binary Search Tree (using C++ vectors with indices, instead of pointers) for the Contest and Competitive Programming course at my university. Thus, I asked myself: "Mhh, I remember that exist a tool to visualize tree better", I was no wrong! But, what was the name? Urgh...

Lost to myself, a thought cross my mind, where I saw that tool? I remember I was watching a video on YouTube, about Control Flow Graphs during compilation phases.

That's it!

The tool was Graphviz!

Graphviz is open source graph visualization software. Graph visualization is a way of representing structural information as diagrams of abstract graphs and networks. It has important applications in networking, bioinformatics, software engineering, database and web design, machine learning, and in visual interfaces for other technical domains.
- The Graphviz Authors (https://www.graphviz.org)

Winnie Pooh thinking — *Me trying to remember the tool's name*

The Code

So, I read the documentation and went straight on to my code. I implemented a BFS traversal into my BST and generated Graphviz code.

  auto printEdge(std::stringstream& stream, NodeIndex from, NodeIndex to) -> void {
    stream << "\t" << from << "->" << to << ";\n";
  }

  auto printInvisibleNode(std::stringstream& stream, NodeIndex from, int& invs) -> void {
    stream << "\t" << invs << "[label=\"/\"];\n";
    stream << "\t" << from << "->" << invs << ";\n";
    invs++;
  }

  auto graphviz() -> std::string {

    int invs = m_nodes.size();

    std::stringstream stream;
    std::deque<NodeIndex> indices{};
    indices.push_back(root);

    stream << "digraph BST {\n\tnode[ shape = plaintext ];\n";

    while (!indices.empty()) {

        auto index = indices.front();
        indices.pop_front();

        stream << "\t" << index << "[label=\"" << m_nodes[index].m_value << "\"];\n";

        if (hasLeftChild(index)) {
            printEdge(stream, index, getLeftChildIndex(index));
            indices.push_back(getLeftChildIndex(index));
        }
        else {
            printInvisibleNode(stream, index, invs);
        }

        if (hasRightChild(index)) {
            printEdge(stream, index, getRightChildIndex(index));
            indices.push_back(getRightChildIndex(index));
        }
        else {
            printInvisibleNode(stream, index, invs);
        }
    }
    
    stream << "}";

    return stream.str();
  }

I think the code is explained by itself. It is a classic BFS and the Graphviz code is emitted using std::stringstream. Let's try the code with a simple BST.

  auto main() -> int {
    
    // Yeah, I know. The namespace's identifier is long
    using BinaryTree = cpc::ds::BinarySearchTreeV<int>;
    
    BinaryTree tree{50, 25, 75, 11, 33, 61, 89, 30, 40, 52, 89, 95};
    std::cout << tree.graphviz(); 
    
    return 0;
  }

And, here it is the output:

Now, putting the code in a Graphviz editor we obtain the following image.

Conclusion

I hope this wall of text (and code) can help someone to visualize a graph-based data structure to understand what is going on.

P.S. I discovered that Eli Bendersky already did an article about this stuff, I leave the link here (take a look!).

visualizing-binary-tree.html (END)

[email protected]: ~/site/blog ❯ less visualizing-binary-tree.html

Visualizing Binary Tree

The Story

The Code

Conclusion