Binary Search Tree

Basic BST with insert, delete, search, min/max, and all four traversal orders.

[Data Structures]|

Jul 9, 2026

|explanatory_notes.md|

#bst#binary-search-tree#traversal

$cat source_code/

cpp

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define sz(x) int(x.size())

struct BST
{
    int data;
    BST *left, *right;

    BST(int data = 0)
    {
        this->data = data;
        left = right = nullptr;
    }

    // Insert New node
    BST *Insert(BST *root, int val)
    {
        if (!root)
            return new BST(val);
        if (val > root->data)
            root->right = Insert(root->right, val);
        else
            root->left = Insert(root->left, val);
        return root;
    }

    // Inorder Traverse (LRR)
    void Inorder(BST *root)
    {
        if (!root)
            return;
        Inorder(root->left);
        cout << root->data << " ";
        Inorder(root->right);
    }

    // Preorde Traverse (RLR)
    void Preorder(BST *root)
    {
        if (!root)
            return;
        cout << root->data << " ";
        Preorder(root->left);
        Preorder(root->right);
    }

    // Postorder Traverse (LRR)
    void Postorder(BST *root)
    {
        if (!root)
            return;
        Postorder(root->left);
        Postorder(root->right);
        cout << root->data << " ";
    }

    // Traverse each level
    void Level_Order(BST *root)
    {
        if (!root)
            return;
        queue<BST *> bfs;
        bfs.push(root);
        while (!bfs.empty())
        {
            BST *curr = bfs.front();
            bfs.pop();
            cout << curr->data << " ";
            if (curr->left)
                bfs.push(curr->left);
            if (curr->right)
                bfs.push(curr->right);
        }
    }

    // Search on a node
    bool Search(BST *root, int val)
    {
        if (!root)
            return false;
        if (root->data == val)
            return true;
        if (val > root->data)
            return Search(root->right, val);
        else
            return Search(root->left, val);
    }

    // Get minimum node in BST
    BST *minValueNode(BST *node)
    {
        BST *current = node;
        while (current && current->left != nullptr)
            current = current->left;
        return current;
    }

    // Get maximum node in BST
    BST *maxValueNode(BST *node)
    {
        BST *current = node;
        while (current && current->right != nullptr)
            current = current->right;
        return current;
    }

    // Delete Node
    BST *Delete_Node(BST *root, int key)
    {
        if (!root)
            return root;
        if (key < root->data)
            root->left = Delete_Node(root->left, key);
        else if (key > root->data)
            root->right = Delete_Node(root->right, key);
        else
        {
            if (!root->left && !root->right)
                return nullptr;
            else if (!root->left)
            {
                BST *temp = root->right;
                free(root);
                return temp;
            }
            else if (!root->right)
            {
                BST *temp = root->left;
                free(root);
                return temp;
            }
            BST *temp = minValueNode(root->right);
            root->data = temp->data;
            root->right = Delete_Node(root->right, temp->data);
        }
        return root;
    }
};

void Solve()
{
    // write your code here
}

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    while (t--)
        Solve();
    return 0;
}

156 linesutf-8

$cat explanation_notes.md

notes_viewer --renderedmarkdown (math enabled)

BST — Binary Search Tree

Constructor

BST* root = nullptr;
BST bst;
root = bst.Insert(root, val);  // insert val, returns new root

Methods

Insert(root, val) — insert val, return new root

Search(root, val) — returns bool

Delete_Node(root, key) — delete key, return new root

minValueNode(node) — leftmost (minimum) node

maxValueNode(node) — rightmost (maximum) node

Inorder(root) — print sorted (ascending)

Preorder(root) — print root-left-right

Postorder(root) — print left-right-root

Level_Order(root) — print BFS order

Example

void Solve()
{
    BST* root = nullptr;
    BST bst;
    root = bst.Insert(root, 5);
    root = bst.Insert(root, 3);
    root = bst.Insert(root, 7);
    bst.Inorder(root);            // 3 5 7
    cout << bst.Search(root, 3);  // 1
    root = bst.Delete_Node(root, 5);
}

Notes

All methods take root pointer as first argument.

Delete_Node handles 3 cases: leaf, one child, two children (inorder successor).

Duplicates go left (when val == root->data).