How to Implement a Binary Search Tree (BST) in C++

To implement a Binary Search Tree (BST) in C++, define a Node struct with data and pointers to left and right children. Then create functions to insert nodes, search values, and traverse the tree recursively or iteratively.

Syntax

A BST node typically contains three parts: the data value, a pointer to the left child, and a pointer to the right child. The tree is built by linking nodes so that left children hold smaller values and right children hold larger values.

Key functions include:

• Insert: Add a new value in the correct position.
• Search: Find if a value exists in the tree.
• Traversal: Visit nodes in order (inorder, preorder, postorder).

cpp

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else if (val > root->data) {
        root->right = insert(root->right, val);
    }
    return root;
}

bool search(Node* root, int val) {
    if (root == nullptr) return false;
    if (root->data == val) return true;
    if (val < root->data) return search(root->left, val);
    else return search(root->right, val);
}

Example

This example shows how to create a BST, insert values, search for a value, and print the tree inorder (sorted order).

cpp

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    if (val < root->data) {
        root->left = insert(root->left, val);
    } else if (val > root->data) {
        root->right = insert(root->right, val);
    }
    return root;
}

bool search(Node* root, int val) {
    if (root == nullptr) return false;
    if (root->data == val) return true;
    if (val < root->data) return search(root->left, val);
    else return search(root->right, val);
}

void inorder(Node* root) {
    if (root == nullptr) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    cout << "Inorder traversal: ";
    inorder(root);
    cout << endl;

    int val = 40;
    cout << "Search " << val << ": " << (search(root, val) ? "Found" : "Not Found") << endl;

    val = 90;
    cout << "Search " << val << ": " << (search(root, val) ? "Found" : "Not Found") << endl;

    return 0;
}

Output

Inorder traversal: 20 30 40 50 60 70 80 
Search 40: Found
Search 90: Not Found

Common Pitfalls

Common mistakes when implementing BSTs include:

• Not handling the nullptr case when inserting or searching, causing crashes.
• Inserting duplicate values without a clear rule, which can break BST properties.
• Forgetting to update child pointers after recursive insertions.
• Not freeing memory, leading to memory leaks (important in real applications).

cpp

/* Wrong: Not updating child pointers on insert */
Node* insert_wrong(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    if (val < root->data) {
        insert_wrong(root->left, val); // Missing assignment
    } else if (val > root->data) {
        insert_wrong(root->right, val); // Missing assignment
    }
    return root;
}

/* Correct: Update child pointers */
Node* insert_correct(Node* root, int val) {
    if (root == nullptr) {
        return new Node(val);
    }
    if (val < root->data) {
        root->left = insert_correct(root->left, val);
    } else if (val > root->data) {
        root->right = insert_correct(root->right, val);
    }
    return root;
}

Quick Reference

• Node struct: Holds data and pointers to left and right children.
• Insert: Recursively place new value in left or right subtree.
• Search: Recursively check left or right subtree based on value.
• Traversal: Inorder traversal prints values sorted.
• Memory: Remember to delete nodes if managing memory manually.

Key Takeaways

Define a Node struct with data and left/right pointers to build the BST.

Use recursive insert and search functions to maintain BST properties.

Always update child pointers when inserting new nodes.

Perform inorder traversal to get sorted output from the BST.

Handle nullptr cases carefully to avoid crashes.