BST Implemenation

To implement a binary search tree, we are going to borrow some concepts from linked lists as there are some parts that are very similar. In these notes we will look a few of the functions and leave the rest as an exercise.

Similar to a linked list, A binary search tree is made up of nodes. Each node can have a left or right child, both of which could be empty trees. Empty trees are represented as nullptrs. The binary search tree object itself only stores a single pointer that points at the root of the entire tree. The data stored within the nodes must be of some type that is comparable. We will thus begin our binary search tree class declaration in a similar manner to that of a linked list. The code for each of the functions will be filled in later in this chapter.

template <typename T>
class BST{
    struct Node{
        T data_;
        Node* left_;
        Node* right_;
        Node(const T& data, Node* left=nullptr, Node* right=nullptr){
            data_=data;
            left_=left;
            right_=right;
        }        
    };
    //single data member pointing to root of tree
    Node* root_; 
public:
    BST(){...}
    void insert(const T& data){...}
    bool search(const T& data) const {...}
    void breadthFirstPrint() const {...}
    void inOrderPrint() const {...}
    void preOrderPrint() const {...}

    ~BST(){...}
};

If you rename the data members above you actually see that its pretty similar to that of a doubly linked list... The key to the operations of a BST lies not in what data is declared, but rather how we organize the nodes. The next 2 sections of the notes we will look at the implementation of the functions listed as public member functions above. In some cases a function may be written both iteratively and recursively and both versions will be looked at