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; there 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 of 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 diagram below.

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 structs? The code looks a lot like a class definition.
Yes, it's similar. You did see it in HW5, but we'll explain it again in a moment. But, in short, it's gathering together three pieces of data to make a Node type.

You see that a Node has a key and two Node*s pointing to its children.

The enclosing class IntTree has a Node* data member root_ pointing to the root node of the whole tree. (We could have gone further and stored other useful information about the tree as a whole, such as a size_ data member to track the total number of nodes, but to keep things minimal, we haven't done that.)

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 did mention 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. In C there is no such thing as private data and structs don't have member functions; external code operates on the data in a struct.

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:

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 that 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 what 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 IntTreeclass, 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 everyone else can't see our Nodes, it doesn't matter that a Node's data is public—it's only “public” for us, which is still pretty private.
I see, so it's a bit like my sister. She'll tell embarrasing stories about me to anyone who asks, but she lives in a secluded mansion, so you'll never meet her, so my secrets are safe!
Sure… The point is that we can use a struct 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.