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.

Python

class BST:
    class Node:
        # Node's init function
        def __init__(self,data=None,left=None,right=None):
            self.data = data
            self.left = left
            self.right = right

    #BST's init function
    def __init__(self):
        self.root = None

    def insert(self, data):
        ...
    
    def search(self, data):
        ...
    
    def inorder_print(self):
        ...

    def pre_order_print(self):
        ...

    def breadthfirst_print(self):
        ...

C++

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 above. In some cases a function may be written both iteratively and recursively and both versions will be looked at

Constructor (C++)

When we create our tree, we are going to start with an empty tree. Thus, our constructor simply needs to initialize the data member to nullptr.

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(){
        root_=nullptr;
    }
...
};