Encoding a BST in C++

There are, of course, many ways to organize a BST structure in C++.
Today we'll focus on a design that is similar to the linked list you built in HW5.

When we thought about BSTs conceptually, we just thought about tree nodes, but when we encode BSTs in C++, we need to adapt the encoding to wrap everything inside a class that represents an entire BST. We did the same thing previously for our C++ linked-list encoding: we had an IntList class that represented a whole list and had a private type for the list nodes. For our C++ encoding of trees, we'll have a class IntTree that provides the interface for the BST as a whole and keeps track of any information that needs to be tracked for the entire tree, and then a nested type Node to represent the nodes of the tree.

The C++ encoding is contrasted with the conceptual one in the following diagram:

class IntTree {
 public: ...
 private:
    // Encoding for a tree node
    struct Node {
        int key_;
        Node* left_;
        Node* right_;
    };

    // The tree object owns all the nodes, and has a pointer to the root node.
    Node* root_;
};

What's the deal with the struct? That code looks a lot like a class definition.
Yes, it is similar. You actually saw it in HW5, but we'll explain it again in a moment.
Basically, it's gathering together three pieces of data to make a Node type.

From the code you can see that a Node has a key and two Node*s pointing to its children.

The enclosing IntTree class has a Node* data member, root_, which points to the root node of the whole tree. (We could go further and store other useful information about the tree as a whole, such as a size_ data member to track the total number of nodes, but we'll keep things simple for now.)

You might have a few different ideas, but setting a pointer to nullptr is the standard way to say “there isn't one”. So we'll set root_ = nullptr for an empty tree, and also use nullptr for nonexistent children in Nodes.

So, what's the difference between a struct and a class?

`struct` vs `class`

struct comes from C++'s C heritage…
I figured that was coming.
We mentioned this in HW5, but let's go over it again…

History: `struct` in C

In C, a struct is just used to aggregate multiple data members together into a single thing. C doesn't support “private data” and structs don't have member functions; instead, the data in a struct is manipulated by external code.

Technical Similarities

From a technical perspective, in C++, structs can do anything classes can do, but there are a couple of minor differences that preserve backwards compatibility with C:

In a struct, data members are public by default. (In a class they are private by default.)
The class and struct keywords are not interchangeable. If you forward declare something as a struct, you must later define it as a struct (and the same with class).

So we could have defined Node as

class Node {
  public:
    int key_;
    Node* left_;
    Node* right_;
};

…but C++ programmers would look at us funny.

Cultural Differences

Culturally speaking, a class encapsulates code and data together to form a cohesive self-contained thing. Usually a class keeps its data private and provides a well-defined interface.

C++ programmers use a struct when they want to gather data together, but don't want or need to make a free-standing class with its own interface. Code that needs to manipulate this data can do so in whatever way it chooses because the data is public.

In short,

Instances of classes can take care of themselves.
Data bound together as a struct is “just the data, no other baggage”.

Wait, isn't it bad that all the data members in our Node struct are public? Doesn't that mean that code outside of our IntTree class can change it?
It would, except that Node is defined privately inside the IntTree class, and no one else ever sees our Node type. We could rename Node to Fufferdoozle and they'd never know!
I have a fufferdoozle, but I do indeed keep mine very private.
Sure… Anyhow, if no-one else can see our Nodes, it doesn't matter that a Node's data is public—it's really only “public” for us, which is still pretty private.
I see. So it's a bit like my sister: She'll tell embarrassing stories about me to anyone who asks, but she lives in a secluded mansion, so you'll never meet her, therefore my secrets are safe!
Um, okay… The point is that we can use a struct here to gather data together, and it's okay if the data is public because no one other than our IntTree class can ever see it.