BST — Core Structure and Methods

In this section, we’re going to build a basic Binary Search Tree (BST) from scratch using a simple class and implement the most important recursive operations.

The Basic Structure of a BST Class

We’ll start by defining a simple Node struct and a Bstree class that holds the root pointer.

Create a private structure inside of the class — this will be used for each node of the tree.

Each Node contains:

• data to hold the value stored in the node

• Node* left to point to the left child

• Node* right to point to the right child

Then we create a Node* root which will point to the starting node of the tree. This is the very first node that gets inserted — and all other nodes branch from it.

Here’s what that setup looks like:

template<typename T>
class Bstree {
private:
    struct Node {
        T data;
        Node* left;
        Node* right;
        Node(T val) : data(val), left(nullptr), right(nullptr) {}
    };

    Node* root;
    // The recursive functions can go here

public:
    Bstree() : root(nullptr) {}
    // The function wrappers can go here
};

Inserting a Value into the BST

To insert a new value into the Binary Search Tree, we need to follow the BST rule:

• If the value is less than the current node’s value, we move left

• If the value is greater than the current node’s value, we move right

• When we reach a null spot (an empty branch), that’s where we create the new node

So we’re checking:

• Is this spot empty? If yes then insert the value here.

• If not, we keep going down the left or right subtree recursively until we find the correct spot.

This function is written as a recursive function that starts at the root and keeps calling itself on the left or right until the value is inserted.

Here’s how we write it:

template<typename T>
void Bstree<T>::insert(T item) {
    root = insert(root, item);
}

This is a small public function that starts the process. It calls the actual recursive logic that does the work:

template<typename T>
typename Bstree<T>::Node* Bstree<T>::insert(Node* node, T item) {
    if (!node) {
        // We’ve found an empty spot — create and return the new node
        return new Node(item);
    }

    if (item < node->data) {
        // Go left if the value is smaller
        node->left = insert(node->left, item);
    } else if (item > node->data) {
        // Go right if the value is larger
        node->right = insert(node->right, item);
    }

    // Return the unchanged node pointer so it reconnects properly
    return node;
}