6.2 ~55 min medium

Binary Search Tree

Left is smaller, right is bigger. Insert, search, find min and max by walking one path, and why the tree's shape decides whether that is O(log n) or O(n).

Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.

02Mental model

Think of a guessing game: “I’m thinking of a number. Is it 50?” “Lower.” “30?” “Higher.” Each answer throws away half the possibilities. That is binary search (Chapter 3), but stored as a tree so that inserting is also fast.

The BST property

For every node:

everything in its left subtree is smaller,
everything in its right subtree is bigger.

(Duplicates: this site ignores them. Some courses send them right. Say which rule you use.)

Search, insert, min, max

All four start at the root and walk down one path:

search(x): equal → found; smaller → go left; bigger → go right; hit nullptr → not found.
insert(x): search for x; where you fall off the tree (nullptr), put the new node.
min: keep going left. max: keep going right.

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

The shape matters

Each step goes down one level, so the cost is the height h. A bushy, balanced tree has h ≈ log₂ n (a million items in about 20 steps). But inserting already-sorted data makes every node go right. The “tree” becomes a linked list, and search is O(n). (Self-balancing trees fix this, but they are beyond this course.)

A free sort

Inorder traversal (left, node, right) visits a BST in sorted order. See the Traversals topic.

03Visualize

space play · ←→ step · r reset. The highlighted code line follows each step.

Loading visualizer…

Insert 45 and watch it go left, right, left. Then try the "Skewed" preset to see a tree turn into a list.

04C++ code

Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.

bst.cpp53 lines · C++17

Compiler ExplorerRun OnlineGDB

#include <iostream>
using namespace std;

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

Node* insert(Node* root, int x) {
    if (root == nullptr) return new Node{x, nullptr, nullptr};
    if (x < root->data) root->left = insert(root->left, x);
    else if (x > root->data) root->right = insert(root->right, x);
    return root;                       // duplicates are ignored
}

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

Node* findMin(Node* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

Node* findMax(Node* root) {
    while (root->right != nullptr) root = root->right;
    return root;
}

void inorder(Node* r) {
    if (!r) return;
    inorder(r->left);
    cout << r->data << " ";
    inorder(r->right);
}

void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }

int main() {
    Node* root = nullptr;
    for (int x : {50, 30, 70, 20, 40, 60, 80, 45})
        root = insert(root, x);
    cout << "inorder (sorted): ";
    inorder(root);
    cout << "\nsearch 45: " << (search(root, 45) ? "found" : "not found") << "\n";
    cout << "search 65: " << (search(root, 65) ? "found" : "not found") << "\n";
    cout << "min: " << findMin(root)->data << ", max: " << findMax(root)->data << "\n";
    destroy(root);
}

#include <iostream>
using namespace std;

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

Node* insert(Node* root, int x) {
    if (root == nullptr) return new Node{x, nullptr, nullptr};
    if (x < root->data) root->left = insert(root->left, x);
    else if (x > root->data) root->right = insert(root->right, x);
    return root;                       // duplicates are ignored
}

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

Node* findMin(Node* root) {
    while (root->left != nullptr) root = root->left;
    return root;
}

Node* findMax(Node* root) {
    while (root->right != nullptr) root = root->right;
    return root;
}

void inorder(Node* r) {
    if (!r) return;
    inorder(r->left);
    cout << r->data << " ";
    inorder(r->right);
}

void destroy(Node* r) { if (!r) return; destroy(r->left); destroy(r->right); delete r; }

int main() {
    Node* root = nullptr;
    for (int x : {50, 30, 70, 20, 40, 60, 80, 45})
        root = insert(root, x);
    cout << "inorder (sorted): ";
    inorder(root);
    cout << "\nsearch 45: " << (search(root, 45) ? "found" : "not found") << "\n";
    cout << "search 65: " << (search(root, 65) ? "found" : "not found") << "\n";
    cout << "min: " << findMin(root)->data << ", max: " << findMax(root)->data << "\n";
    destroy(root);
}

Expected output

inorder (sorted): 20 30 40 45 50 60 70 80 
search 45: found
search 65: not found
min: 20, max: 80

05Complexity

search / insert, balanced	O(log n)
search / insert, skewed	O(n)
min / max	O(h)
inorder (sorted output)	O(n)
Extra space	O(n) for the nodes, O(h) recursion

Every operation walks one root-to-leaf path, so the cost is the height h. Balanced trees have h ≈ log₂ n; inserting sorted data gives h = n − 1.

06Watch

Binary Search Tree

mycodeschool · 19:27

Why this one: The BST property and why it gives fast search, compared with arrays and lists.

Watched

Binary search tree: Implementation in C/C++

mycodeschool · 18:36

Why this one: Writes recursive insert and search in C/C++ step by step.

Watched

07Exam lens

Likely questions

Insert 50, 30, 70, 20, 40, 60, 80 into an empty BST. Draw it.
Write recursive insert and search for a BST.
How do you find the minimum and maximum of a BST?
What is the worst-case time of BST search? Give an input that causes it.
Why does inorder traversal of a BST give sorted output?

Common mistakes

Writing insert(root->left, x); without assigning the result back to root->left.
Checking only a node's children, not the whole subtree, when asked "is this a BST?".
Forgetting the nullptr check before reading root->data.
Saying BST search is always O(log n). That only holds for a balanced tree.

08Quick check

1.In the BST built from 50, 30, 70, 20, 40, 60, 80, where does 45 go?
2.The minimum value in a BST is…
3.Inserting 10, 20, 30, 40, 50 into an empty BST produces…
4.Why must you write root->left = insert(root->left, x);?

09Practice

🟢 Trace by hand

Insert 40, 20, 60, 10, 30, 50, 70, 25 into an empty BST. Then trace search(25) and search(55), listing every node visited.

Show answer

        40
      /    \
    20      60
   /  \    /  \
  10  30  50  70
     /
    25

search(25): 40 → 20 → 30 → 25 found (4 nodes)
search(55): 40 → 60 → 50 → right of 50 is null, not found

🟡 Implement it

Write iterative bool search(Node* root, int x) (no recursion), and int countInRange(Node* r, int lo, int hi).

Hint

Iterative: while (root) { if (x == root->data) return true; root = x < root->data ? root->left : root->right; }. Range: skip the left subtree when r->data < lo.

🔴 Solve problems

Search in a Binary Search Tree easyleetcode.com
Hint
This page's search, returning the node instead of a bool.
Insert into a Binary Search Tree mediumleetcode.com
Hint
Exactly insert() from this page. It is rated medium but it is a 5-line function.
Validate Binary Search Tree mediumleetcode.com
Hint
Pass down allowed bounds: valid(node, lo, hi). Left gets (lo, node->val), right gets (node->val, hi). Use long long for the bounds.

10Mastery checklist

Tick these honestly. When every box is ticked, the topic is marked complete.

I can build a BST from a list of numbers by hand.
I can write recursive insert and search.
I can find the min and max.
I can explain why BST operations are O(h) and when h becomes n.

0/4 ticked

My notes

View as Markdown · Chapter cheat sheet