Binary Search Tree

Introduction to Binary Search Tree

8 min board

What to say

A Binary Search Tree is a binary tree in which every node holds a key and the keys obey one ordering property.
All nodes in the left subtree of a node are less than or equal to it; all nodes in the right subtree are strictly greater. The whole subtree, not only the child.
Someone will ask about equal keys — answer with the three options on the second card, and say which one today's code uses: equal keys go left.
That property is what makes search, insertion and deletion efficient — especially while the tree stays balanced.

The ordering property

Left subtree — every key less than or equal to the node's key (≤).
Right subtree — every key strictly greater than the node's key (>).

Draw it for the keys of today's program, 10 15 16 13 12 14 9 8 17:

        10
       /  \
      9    15
     /    /  \
    8    13   16
        /  \    \
       12  14    17

Check the rule at 15: its left subtree is 13, 12, 14 — all smaller; its right subtree is 16, 17 — all larger. And the whole right half of the tree is larger than the root 10.

What about equal keys?

The rule has to say where a key equal to the node goes. There are three usual answers — pick one and use it in every function: insert, search and delete.

Option	In insert	Left / right rule	Like
1 · No duplicates	`if (data == node->data) return node;`	left < node < right	`std::set`
2 · Equal keys go left	`if (data <= node->data)` → left	left ≤ node < right	today's code
3 · A counter in the node	`if (data == node->data) { node->cnt++; return node; }`	left < node < right	`std::multiset`

Option 2 is what today's program does. In-order still comes out sorted, with equal keys next to each other; search stops at the highest copy. That is why main, which inserts 10 three times, prints 8 9 10 10 10 12 ….

Option 3 keeps the tree small when there are many repeats: delete decrements cnt and removes the node only when it reaches 0.

BST Properties

12 min demo: tree builder

What to say

In-order traversal of a BST gives the elements in sorted order. Show it: build a tree in the demo and run in-order.
Search, insert and delete are O(log n) on average — each step goes down one level.
The worst case is O(n) — a skewed tree. Press sorted 1…10: the tree becomes a diagonal, height 10 instead of 4.
Space is O(n) — one node per key.

Four facts

Property	Value
In-order traversal	elements in sorted order
Search, insert, delete — average	O(log n)
Search, insert, delete — worst (skewed tree)	O(n)
Space for n nodes	O(n)

Demo · the tree, live

key

speed

nodes

height h

⌈log₂(n+1)⌉ ideal

comparisons, last op

—

Type a key and press insert. The walk down is animated — that walk is the algorithm.

visit order

Complete BST Implementation

35 min code

What to say

Write the program top to bottom, one function at a time: the node, the class, insert, traversals, min and max, search, delete, height and count, then main.
Every recursive function has the same shape: stop at NULL, otherwise go left or right by comparing with the key.
Insert returns the (sub)tree root and the caller reattaches it: node->left = insert(node->left, data). The same trick is used by delete.
Then show two more versions of the same program: the loop version of insert and of find_min next to the recursive ones — the same walk down, written two ways.

1 · The node

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left, *right;

    Node(int data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

A key and two pointers. A new node has no children, so both start as NULL.

2 · The tree and insert

class BST {
    public:
    Node *root;

    BST() {
        root = NULL;
    }
    ...
};

// Insert operation - O(log n) average, O(n) worst case
Node *insert(Node *node, int data) {
    if (node == NULL) {
        node = new Node(data);
        return node;
    }

    if (data <= node->data) 
        node->left = insert(node->left, data);
    else
        node->right = insert(node->right, data);

    return node;
}

Walk down until a NULL, create the node there, and return it so the parent links it in. Equal keys go left here (<=).

3 · Traversals

// In-order traversal - gives sorted output
void inOrder(Node *node) {
    if (node == NULL)
        return;
    inOrder(node->left);
    cout << node->data << " ";
    inOrder(node->right);
}

// Pre-order traversal
void preOrder(Node *node) {
    if (node == NULL)
        return;
    cout << node->data << " ";
    preOrder(node->left);
    preOrder(node->right);
}

// Post-order traversal
void postOrder(Node *node) {
    if (node == NULL)
        return;
    postOrder(node->left);
    postOrder(node->right);
    cout << node->data << " ";
}

Three functions, one difference: where the cout line stands — between the calls, before them, or after them.

4 · Minimum, maximum, search

// Find minimum element - leftmost node
Node *findMin(Node *node) {
    if (node == NULL)
        return NULL;
    while (node->left != NULL)
        node = node->left;
    return node;
}

// Find maximum element - rightmost node
Node *findMax(Node *node) {
    if (node == NULL)
        return NULL;
    while (node->right != NULL)
        node = node->right;
    return node;
}

// Search for a value
Node *search(Node *node, int data) {
    if (node == NULL || node->data == data)
        return node;
    
    if (data < node->data)
        return search(node->left, data);
    else
        return search(node->right, data);
}

Minimum is the leftmost node, maximum the rightmost. Search is insert without the insertion: stop when the key matches or the pointer is NULL.

5 · Delete

// Delete operation
Node *deleteNode(Node *node, int data) {
    if (node == NULL)
        return NULL;
    if (data < node->data)
        node->left = deleteNode(node->left, data);
    else if (data > node->data)
        node->right = deleteNode(node->right, data);
    else {
        if (node->right == NULL and node->left == NULL)
            node = NULL;
        else if (node->left == NULL)
            node = node->right;
        else if (node->right == NULL)
            node = node->left;
        else {
            Node *tmp = findMin(node->right);
            node->data = tmp->data;
            node->right = deleteNode(node->right, tmp->data);
        }
    }
    return node;
}

Find the node as in search, then one of the cases. With two children the node takes the key of its in-order successor — the minimum of the right subtree — and that node is deleted from the right subtree instead. The cases are drawn step by step in Deletion Cases in Detail.

6 · Height and node count

// Helper function to get height of tree
int getHeight(Node *node) {
    if (node == NULL)
        return 0;
    return 1 + max(getHeight(node->left), getHeight(node->right));
}

// Count total nodes in tree
int countNodes(Node *node) {
    if (node == NULL)
        return 0;
    return 1 + countNodes(node->left) + countNodes(node->right);
}

Both are "answer for the left + answer for the right + this node". An empty tree has height 0 and 0 nodes.

7 · main — and what it prints

int main() {
    BST *bst = new BST();
    
    // Insert nodes
    bst->root = bst->insert(bst->root, 10);
    bst->root = bst->insert(bst->root, 15);
    bst->root = bst->insert(bst->root, 16);
    bst->root = bst->insert(bst->root, 13);
    bst->root = bst->insert(bst->root, 12);
    bst->root = bst->insert(bst->root, 14);
    bst->root = bst->insert(bst->root, 9);
    bst->root = bst->insert(bst->root, 8);
    bst->root = bst->insert(bst->root, 10);  // Duplicate - goes to left
    bst->root = bst->insert(bst->root, 10);  // Another duplicate
    bst->root = bst->insert(bst->root, 17);

    cout << "In-order traversal (sorted): ";
    bst->inOrder(bst->root);
    cout << endl;

    cout << "Pre-order traversal: ";
    bst->preOrder(bst->root);
    cout << endl;

    cout << "Post-order traversal: ";
    bst->postOrder(bst->root);
    cout << endl;

    // Find min and max
    Node *node_min = bst->findMin(bst->root);
    Node *node_max = bst->findMax(bst->root);
    cout << "Min: " << node_min->data << ", Max: " << node_max->data << endl;

    // Search for a value
    Node *found = bst->search(bst->root, 13);
    if (found)
        cout << "Found: " << found->data << endl;
    else
        cout << "Not found" << endl;

    // Tree statistics
    cout << "Tree height: " << bst->getHeight(bst->root) << endl;
    cout << "Total nodes: " << bst->countNodes(bst->root) << endl;

    // Delete a node
    cout << "Deleting node 13..." << endl;
    bst->root = bst->deleteNode(bst->root, 13);
    cout << "In-order after deletion: ";
    bst->inOrder(bst->root);
    cout << endl;

    return 0;
}

output

In-order traversal (sorted): 8 9 10 10 10 12 13 14 15 16 17
Pre-order traversal: 10 9 8 10 10 15 13 12 14 16 17
Post-order traversal: 8 10 10 9 12 14 13 17 16 15 10
Min: 8, Max: 17
Found: 13
Tree height: 4
Total nodes: 11
Deleting node 13...
In-order after deletion: 8 9 10 10 10 12 14 15 16 17

Besides the nine keys, main inserts 10 twice more. Equal keys go left, so in-order prints three 10s and the height is 4.

The whole program

Everything above in one file — open it and press ▶ edit & run.

BST — the full program186 lines

#include <iostream>
using namespace std;

class Node {
    public:
    int data;
    Node *left, *right;

    Node(int data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

class BST {
    public:
    Node *root;

    BST() {
        root = NULL;
    }

    // Insert operation - O(log n) average, O(n) worst case
    Node *insert(Node *node, int data) {
        if (node == NULL) {
            node = new Node(data);
            return node;
        }

        if (data <= node->data) 
            node->left = insert(node->left, data);
        else
            node->right = insert(node->right, data);

        return node;
    }

    // In-order traversal - gives sorted output
    void inOrder(Node *node) {
        if (node == NULL)
            return;
        inOrder(node->left);
        cout << node->data << " ";
        inOrder(node->right);
    }

    // Pre-order traversal
    void preOrder(Node *node) {
        if (node == NULL)
            return;
        cout << node->data << " ";
        preOrder(node->left);
        preOrder(node->right);
    }

    // Post-order traversal
    void postOrder(Node *node) {
        if (node == NULL)
            return;
        postOrder(node->left);
        postOrder(node->right);
        cout << node->data << " ";
    }

    // Find minimum element - leftmost node
    Node *findMin(Node *node) {
        if (node == NULL)
            return NULL;
        while (node->left != NULL)
            node = node->left;
        return node;
    }

    // Find maximum element - rightmost node
    Node *findMax(Node *node) {
        if (node == NULL)
            return NULL;
        while (node->right != NULL)
            node = node->right;
        return node;
    }

    // Search for a value
    Node *search(Node *node, int data) {
        if (node == NULL || node->data == data)
            return node;
        
        if (data < node->data)
            return search(node->left, data);
        else
            return search(node->right, data);
    }

    // Delete operation
    Node *deleteNode(Node *node, int data) {
        if (node == NULL)
            return NULL;
        if (data < node->data)
            node->left = deleteNode(node->left, data);
        else if (data > node->data)
            node->right = deleteNode(node->right, data);
        else {
            if (node->right == NULL and node->left == NULL)
                node = NULL;
            else if (node->left == NULL)
                node = node->right;
            else if (node->right == NULL)
                node = node->left;
            else {
                Node *tmp = findMin(node->right);
                node->data = tmp->data;
                node->right = deleteNode(node->right, tmp->data);
            }
        }
        return node;
    }

    // Helper function to get height of tree
    int getHeight(Node *node) {
        if (node == NULL)
            return 0;
        return 1 + max(getHeight(node->left), getHeight(node->right));
    }

    // Count total nodes in tree
    int countNodes(Node *node) {
        if (node == NULL)
            return 0;
        return 1 + countNodes(node->left) + countNodes(node->right);
    }
};

int main() {
    BST *bst = new BST();
    
    // Insert nodes
    bst->root = bst->insert(bst->root, 10);
    bst->root = bst->insert(bst->root, 15);
    bst->root = bst->insert(bst->root, 16);
    bst->root = bst->insert(bst->root, 13);
    bst->root = bst->insert(bst->root, 12);
    bst->root = bst->insert(bst->root, 14);
    bst->root = bst->insert(bst->root, 9);
    bst->root = bst->insert(bst->root, 8);
    bst->root = bst->insert(bst->root, 10);  // Duplicate - goes to left
    bst->root = bst->insert(bst->root, 10);  // Another duplicate
    bst->root = bst->insert(bst->root, 17);

    cout << "In-order traversal (sorted): ";
    bst->inOrder(bst->root);
    cout << endl;

    cout << "Pre-order traversal: ";
    bst->preOrder(bst->root);
    cout << endl;

    cout << "Post-order traversal: ";
    bst->postOrder(bst->root);
    cout << endl;

    // Find min and max
    Node *node_min = bst->findMin(bst->root);
    Node *node_max = bst->findMax(bst->root);
    cout << "Min: " << node_min->data << ", Max: " << node_max->data << endl;

    // Search for a value
    Node *found = bst->search(bst->root, 13);
    if (found)
        cout << "Found: " << found->data << endl;
    else
        cout << "Not found" << endl;

    // Tree statistics
    cout << "Tree height: " << bst->getHeight(bst->root) << endl;
    cout << "Total nodes: " << bst->countNodes(bst->root) << endl;

    // Delete a node
    cout << "Deleting node 13..." << endl;
    bst->root = bst->deleteNode(bst->root, 13);
    cout << "In-order after deletion: ";
    bst->inOrder(bst->root);
    cout << endl;

    return 0;
}

Another version · insert with a loop

The same step can be written two ways. Insert with a loop instead of recursion:

void insert_node2(int data) {
    if (this->root == NULL) {
        this->root = new Node(data);
        return;
    }
    Node *cur = root;
    while (cur != NULL) {
        if (data > cur->data) {
            if (cur->right == NULL) {
                cur->right = new Node(data);
                break;
            } else
                cur = cur->right;
        } else {
            if (cur->left == NULL) {
                cur->left = new Node(data);
                break;
            } else 
                cur = cur->left;
        }
    }
}

and the minimum, recursive and with a loop:

Node* find_min(Node *node) {
    if (node->left == NULL)
        return node;
    return find_min(node->left);
}

Node *find_min2(Node *node) {
    while (node->left != NULL)
        node = node->left;
    return node;
}

the full program — version 2122 lines

#include <iostream>

using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
    Node *parent;
    Node(int data) {
        this->data = data;
        left = NULL;
        right = NULL;
    }
};

class Tree {
    public:
    Node *root;

    Node* insert_node(Node *node, int data) {
        if (node == NULL) {
            Node *node = new Node(data);
            return node;
        }
        if (node->data < data) 
            node->right = insert_node(node->right, data);
        else
            node->left = insert_node(node->left, data);
        return node;
    }

    void insert_node2(int data) {
        if (this->root == NULL) {
            this->root = new Node(data);
            return;
        }
        Node *cur = root;
        while (cur != NULL) {
            if (data > cur->data) {
                if (cur->right == NULL) {
                    cur->right = new Node(data);
                    break;
                } else
                    cur = cur->right;
            } else {
                if (cur->left == NULL) {
                    cur->left = new Node(data);
                    break;
                } else 
                    cur = cur->left;
            }
        }
    }

    void in_order(Node *node) {
        if (node == NULL)
            return;
        in_order(node->left);
        cout << node->data << " ";
        in_order(node->right);
    }

    Node* find_min(Node *node) {
        if (node->left == NULL)
            return node;
        return find_min(node->left);
    }

    Node *find_min2(Node *node) {
        while (node->left != NULL)
            node = node->left;
        return node;
    }

    Node *delete_node(Node *node, int data) {
        if (node == NULL)
            return NULL;
        if (data < node->data)
            node->left = delete_node(node->left, data);
        else if (data > node->data)
            node->right = delete_node(node->right, data);
        else {
            if (node->right == NULL and node->left == NULL)
                node = NULL;
            else if (node->left == NULL) 
                node = node->right;
            else if (node->right == NULL)
                node = node->left;
            else {
                Node *tmp = find_min(node->right);
                node->data = tmp->data;
                node->right = delete_node(node->right, tmp->data);
            }
        }
        return node;
    }
};

int main() {
    Tree *tree = new Tree();
    // tree->root = tree->insert_node(NULL, 10);
    // tree->root = tree->insert_node(tree->root, 8);
    // tree->root = tree->insert_node(tree->root, 20);
    // tree->root = tree->insert_node(tree->root, 7);
    // tree->root = tree->insert_node(tree->root, 9);
    tree->insert_node2(10);
    tree->insert_node2(8);
    tree->insert_node2(20);
    tree->insert_node2(7);
    tree->insert_node2(9);

    // cout << tree->root->left->right->data;
    // tree->in_order(tree->root);
    Node *node = tree->find_min(tree->root);
    cout << node->data;
    
    

    return 0;
}

output

Another version · Tree with a constructor

A third version: a constructor for Tree, one recursive insert, find_min, find_max and the same delete with the successor. main builds 30 20 40 10 26 34 45 9 12 and prints the maximum.

the full program — version 398 lines

#include <iostream>

using namespace std;

class Node {
    public:
    int data;
    Node *left;
    Node *right;
    // Node *parent;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

class Tree {
    public:
    Node *root;
    Tree() {
        this->root = NULL;
    }

    Node* insert(Node *node, int data) {
        if (node == NULL) {
            node = new Node(data);
            return node;
        }
        if (data > node->data) 
            node->right = insert(node->right, data);
        else 
            node->left = insert(node->left, data);
        return node;
    }

    void in_order(Node *node) {
        if (node == NULL)
            return;
        in_order(node->left);
        cout << node->data << " ";
        in_order(node->right);
    }

    Node* find_min(Node *node) {
        if (node->left == NULL)
            return node;            
        return find_min(node->left);
    }
    Node* find_max(Node *node) {
        if (node->right == NULL)
            return node;
        return find_max(node->right);
    }

    Node* delete_node(Node *node, int data) {
        if (node == NULL)
            return NULL;
        if (data > node->data) 
            node->right = delete_node(node->right, data);
        else if (data < node->data)
            node->left = delete_node(node->left, data);
        else {
            // node->data = data
            if (node->left == NULL && node->right == NULL)
                return NULL;
            else if (node->left == NULL)
                node = node->right;
            else if (node->right == NULL)
                node = node->left;
            else {
                Node *tmp = find_min(node->right);
                node->data = tmp->data;
                node->right = delete_node(node->right, tmp->data);
            }
        }
        return node;   // added: without it the caller gets garbage
    }
};

int main() {
    Tree *tree = new Tree();
    tree->root = tree->insert(tree->root, 30);
    tree->root = tree->insert(tree->root, 20);
    tree->root = tree->insert(tree->root, 40);
    tree->root = tree->insert(tree->root, 10);
    tree->root = tree->insert(tree->root, 26);
    tree->root = tree->insert(tree->root, 34);
    tree->root = tree->insert(tree->root, 45);
    tree->root = tree->insert(tree->root, 9);
    tree->root = tree->insert(tree->root, 12);
    // cout << tree->root->left->right->data;
    // tree->in_order(tree->root);
    // Node *node = tree->find_min(tree->root);
    Node *node = tree->find_max(tree->root);
    cout << node->data;
    return 0;
}

output

Tree Traversals

10 min board

What to say

In-order — left, root, right. The result is the elements in sorted order; use it to get a sorted sequence from a BST.
Pre-order — root, left, right. The root comes first; use it to create a copy of the tree.
Post-order — left, right, root. The root comes last; use it to delete the tree safely — children before the parent.

Three orders

Traversal	Order	Result	Use case
In-order	Left → Root → Right	elements in sorted order	sorted sequence from a BST
Pre-order	Root → Left → Right	root comes first	creating a copy of the tree
Post-order	Left → Right → Root	root comes last	deleting the tree safely

On the tree from the introduction:

in-order    8 9 10 12 13 14 15 16 17
pre-order   10 9 8 15 13 12 14 16 17
post-order  8 9 12 14 13 17 16 15 10

BST Operations Analysis

6 min board

What to say

Every operation except traversal walks one path from the root, so its cost is the height of the tree.
Best case — the key is at the root. Average — a tree built from random order, height about log n. Worst — the skewed tree, height n.

Cost of each operation

Operation	Average case	Worst case	Best case
Search	O(log n)	O(n)	O(1)
Insert	O(log n)	O(n)	O(1)
Delete	O(log n)	O(n)	O(1)
Find Min	O(log n)	O(n)	O(1)
Find Max	O(log n)	O(n)	O(1)
Traversal	O(n)	O(n)	O(n)

Deletion Cases in Detail

15 min board

What to say

Case 1 — a leaf. Simply remove the node. Example: delete 8.
Case 2 — one child. Replace the node with its child. Example: delete 9 — it has only the left child 8.
Case 3 — two children. Find the in-order predecessor (the rightmost node of the left subtree) or the in-order successor (the leftmost node of the right subtree), copy its value into the node, then delete the predecessor or successor.
The predecessor has no right child, the successor no left child — so deleting it is always case 1 or 2.

Case 1 · a leaf

Simply remove the node. On the tree from the introduction: delete 8 — 9 loses its left child, nothing else changes.

Case 2 · one child

Replace the node with its child. Delete 9 — it has only the left child 8, so 8 takes its place under 10.

Case 3 · two children

Find the in-order predecessor — the rightmost node in the left subtree — or the in-order successor — the leftmost node in the right subtree.
Replace the node's data with the predecessor's / successor's.
Delete the predecessor / successor.

Delete 15 with the successor, as deleteNode above does: the leftmost key of its right subtree is 16. 16 moves up into 15's place, and 17 takes the old place of 16.

        10                        10
       /  \                      /  \
      9    15          →        9    16
     /    /  \                 /    /  \
    8    13   16              8    13   17
        /  \    \                /  \
       12  14    17             12  14

With the predecessor it would be 14 instead — the rightmost key of the left subtree. Both keep the ordering property.

BST vs Other Data Structures

5 min board

What to say

A sorted array searches fast but inserts slowly; a linked list inserts fast but searches slowly. A balanced BST does all three in O(log n).
A hash table is O(1) on average, but it keeps no order.

Side by side

Data Structure	Search	Insert	Delete	Space
Array (unsorted)	O(n)	O(1)	O(n)	O(n)
Array (sorted)	O(log n)	O(n)	O(n)	O(n)
Linked List	O(n)	O(1)	O(n)	O(n)
BST (balanced)	O(log n)	O(log n)	O(log n)	O(n)
Hash Table	O(1)*	O(1)*	O(1)*	O(n)

* average case for a hash table

Advantages and Disadvantages

4 min board

Advantages

Efficient searching: O(log n) average case
In-order traversal gives a sorted sequence
Dynamic size: can grow and shrink during runtime
No extra space needed for sorting

Disadvantages

Can become unbalanced → O(n) worst case
No constant time operations like hash tables
More complex than arrays for simple operations

When to Use BST

4 min board

Good for

Frequent search operations
Need to maintain sorted order
Range queries (find all elements between x and y)
Dynamic data with insertions and deletions

Not ideal for

Mostly sequential access
Frequent random access by index
When constant time operations are critical

Key Takeaways

3 min

Five things to remember

A BST maintains sorted order through its structure property.
Performance depends on tree balance — a balanced tree gives O(log n), a skewed tree gives O(n).
In-order traversal always gives sorted output.
Deletion is the most complex operation, with three different cases.
The BST is the foundation for more advanced trees like AVL and Red-Black trees.

Lab 4 — the problems

8 min ADS-Lab-04

Problem to topic

Mountains

Tree given as edges — follow a path of L/R instructions

Get subtreekey

Build with insert, then the size of one subtree

Christmas Giftskey

Build with insert, then a question about a subtree

Aureole

Level by level — needs a queue (BFS), not in today's code

Width

The widest level — the same queue

Triangle Binary Search Tree

Nodes per depth, n = 10⁴, TL 3 s — heavy

Killua and Hunter exam

Tree diameter, n = 2·10⁴, TL 5 s — heaviest in the lab

Greater Sum Tree

Reverse in-order (right, root, left) with a running sum

More One Night

Insert a permutation, then count something about the shape

K-th element in Binary Search Treekey

k-th smallest — in-order with a counter, stop early