Introduction to Binary Search Trees

Say you have a plain binary tree full of numbers. Now someone asks you a simple question. “Is 57 in this tree?” What do you do? You have no choice. You walk every single node and check each one until you find it or run out. That is slow. If the tree has a million numbers, you might look at a million nodes.

A binary search tree fixes exactly this problem. It keeps the numbers in a smart order so you never have to look at the whole tree. At each step you can throw away half of what is left. That is what we will learn here.

📖 What Is a Binary Search Tree?

A binary search tree is a binary tree that follows one ordering rule. A binary tree is just a tree where every node has at most two children, a left child and a right child. The “binary search” part adds the rule that keeps things sorted.

Here is the rule, and it is the whole idea:

• For any node, every value in its left subtree is smaller than that node.
• For any node, every value in its right subtree is larger than that node.
• This rule holds for every node, not just the top one.

So smaller things go left. Bigger things go right. Always.

🎯 Why We Need It

Think of a real dictionary. The words are sorted. When you look for “mango” you do not read every word from “apple” onward. You open the middle, see if you have gone too far or not far enough, and jump. You keep cutting the search area in half. That is fast.

A plain tree is like a dictionary with the words thrown in randomly. To find one word you would have to read them all. A BST is the sorted dictionary. The ordering rule is what lets you jump.

Searching a plain tree means you might check every node. That is O(n). The BST ordering rule lets you skip half the nodes that are left at each step. On average that gives you O(log n). That is the whole win.

🌳 A Valid BST

Let’s look at one. Take the numbers 50, 30, 70, 20, 40, 60, 80. Arranged as a BST, they look like this.

Check the rule at the top node, 50. Everything on its left (30, 20, 40) is smaller than 50. Everything on its right (60, 70, 80) is larger than 50. Now check 30. Its left child 20 is smaller, and its right child 40 is larger. Good. Every node passes. So this is a valid BST.

🔍 How Search Becomes Fast

Now let’s actually search. Say we want to find 60 in that tree. Watch how little we look at.

• Start at the root, 50. We want 60. Since 60 is greater than 50, the answer can only be on the right. So we ignore the entire left side.
• Move to 70. Since 60 is less than 70, go left. Ignore 70’s right side.
• Move to 60. Found it.

We touched three nodes, not seven. Every comparison told us which half to drop. That dropping of half is where the O(log n) speed comes from. With a million sorted values in a balanced BST, you would look at around 20 nodes, not a million.

Compare that to a plain unordered tree. There, 60 could be anywhere, so you would have to keep checking node after node. There is no shortcut. That is the O(n) we wanted to escape.

🧱 What a BST Node Looks Like

A BST is built from nodes. Each node holds a value and two links, one to a left child and one to a right child. A link points to nothing when there is no child there. Here is a tiny node definition in all five languages so the structure is clear.

#include <stdio.h>
#include <stdlib.h>

// One node of a BST: a value plus a left and right link.
struct Node {
    int value;
    struct Node* left;
    struct Node* right;
};

// Make a new node with no children yet.
struct Node* newNode(int value) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->value = value;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    struct Node* root = newNode(50);
    root->left = newNode(30);
    root->right = newNode(70);
    printf("Root: %d\n", root->value);
    printf("Left child: %d\n", root->left->value);
    printf("Right child: %d\n", root->right->value);
    return 0;
}

Root: 50
Left child: 30
Right child: 70

#include <iostream>
using namespace std;

// One node of a BST: a value plus a left and right link.
struct Node {
    int value;
    Node* left;
    Node* right;
    Node(int v) : value(v), left(nullptr), right(nullptr) {}
};

int main() {
    Node* root = new Node(50);
    root->left = new Node(30);
    root->right = new Node(70);
    cout << "Root: " << root->value << endl;
    cout << "Left child: " << root->left->value << endl;
    cout << "Right child: " << root->right->value << endl;
    return 0;
}

Root: 50
Left child: 30
Right child: 70

public class BstNode {
    // One node of a BST: a value plus a left and right link.
    static class Node {
        int value;
        Node left;
        Node right;
        Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public static void main(String[] args) {
        Node root = new Node(50);
        root.left = new Node(30);
        root.right = new Node(70);
        System.out.println("Root: " + root.value);
        System.out.println("Left child: " + root.left.value);
        System.out.println("Right child: " + root.right.value);
    }
}

Root: 50
Left child: 30
Right child: 70

# One node of a BST: a value plus a left and right link.
class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = Node(50)
root.left = Node(30)
root.right = Node(70)

print("Root:", root.value)
print("Left child:", root.left.value)
print("Right child:", root.right.value)

Root: 50
Left child: 30
Right child: 70

// One node of a BST: a value plus a left and right link.
class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

const root = new Node(50);
root.left = new Node(30);
root.right = new Node(70);

console.log("Root:", root.value);
console.log("Left child:", root.left.value);
console.log("Right child:", root.right.value);

Root: 50
Left child: 30
Right child: 70

⚠️ When a BST Slows Down

The O(log n) speed is the average case. It only holds when the tree is roughly balanced, meaning the left and right sides are about the same height so the tree stays short and bushy.

But what if you insert numbers in already-sorted order, like 10, 20, 30, 40, 50? Each new number is larger than the last, so it always goes right. You end up with a tree that is just one long line going down.

This is called a skewed tree. It looks more like a linked list than a tree. Now searching has to walk down node by node again. So the speed drops back to O(n), the very thing we were trying to avoid.

Here’s the timing in one table.

🧩 What You’ve Learned

• ✅ A binary search tree is a binary tree with one ordering rule: left subtree smaller, right subtree larger, for every node.
• ✅ That rule keeps the values sorted, so reading left-node-right gives you a sorted list.
• ✅ Searching a plain tree is O(n) because you may check every node.
• ✅ A BST lets you drop half the remaining nodes at each step, giving O(log n) search on average, just like searching a sorted dictionary.
• ✅ A BST node holds a value plus a left link and a right link.
• ✅ If the tree becomes skewed (like inserting sorted numbers), it turns into a line and search slows back to O(n).

🚀 What’s Next?

• Search in a BST
• Insert in a BST