# 6.2 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).

Chapter: Trees · ~55 min · medium
URL: https://dsa.fetehadin.com/learn/bst

## Mental 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**.

```cpp
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.

## C++ code: bst.cpp

```cpp
#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:

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

## Complexity

| Case | Cost |
| --- | --- |
| search / insert, balanced | O(log n) |
| search / insert, skewed | O(n) |
| min / max | O(h) |
| inorder (sorted output) | O(n) |

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.

## Videos

- [Binary Search Tree](https://youtu.be/pYT9F8_LFTM) (mycodeschool): The BST property and why it gives fast search, compared with arrays and lists.
- [Binary search tree: Implementation in C/C++](https://youtu.be/COZK7NATh4k) (mycodeschool): Writes recursive insert and search in C/C++ step by step.

## Exam 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.

## Quick check

1. In the BST built from 50, 30, 70, 20, 40, 60, 80, where does 45 go?
   A. left child of 20
   B. right child of 40
   C. left child of 60
   D. right child of 80
   Answer: B. 45 < 50 go left; 45 > 30 go right; 45 > 40 go right of 40.

2. The minimum value in a BST is…
   A. the root
   B. the leftmost node
   C. any leaf
   D. the rightmost node
   Answer: B. Keep going left until there is no left child.

3. Inserting 10, 20, 30, 40, 50 into an empty BST produces…
   A. a balanced tree of height 2
   B. a right-skewed chain of height 4
   C. a complete tree
   D. an error
   Answer: B. Each value is bigger than all before it, so it always goes right. Search becomes O(n).

4. Why must you write `root->left = insert(root->left, x);`?
   A. Style only
   B. When root->left is null, insert returns the new node, and the parent must link to it
   C. For speed
   D. To balance the tree
   Answer: B. Without the assignment, the new node is created but never attached.

## Practice

**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.

Solution:

```text
        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`.

**Problems:**

- [Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/) (easy). Hint: This page's search, returning the node instead of a bool.
- [Insert into a Binary Search Tree](https://leetcode.com/problems/insert-into-a-binary-search-tree/) (medium). Hint: Exactly `insert()` from this page. It is rated medium but it is a 5-line function.
- [Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) (medium). 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.

## Mastery checklist

- [ ] 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.