A binary search tree keeps keys in order: smaller keys to the left, larger to the right, at every node. That one rule turns search, insert, delete, floor and ceiling into a single walk down one path — O(log n) when the tree is balanced — and makes an inorder traversal print the keys sorted.

The sample BST: an empty tree after inserting 20, 15, 30, 40, 50, 12, 18, 35, 80, 7 in that order

          20
       /      \
     15        30
    /  \         \
  12    18        40
 /               /  \
7              35    50
                       \
                        80

Check the invariant at any node: left of 20 are 15 12 18 7 (all smaller), right are 30 40 35 50 80 (all larger). Left of 40 is 35, right is 50 80. It holds for the whole subtree, not just the two children — a tree where 35 sat under 15 would have every child in order and still be wrong.

Why a BST: comparison with other structures

A BST is the structure for data that must stay sorted while it changes. Arrays are fast at one thing and slow at the other; a hash table is fastest for exact lookups but knows nothing about order.

Operation	Unsorted array	Sorted array	Linked list	BST (balanced)	Hash table
Search	O(n)	O(log n)	O(n)	O(log n)	O(1) average
Insert	O(1)	O(n)	O(1)	O(log n)	O(1) average
Delete	O(n)	O(n)	O(n)	O(log n)	O(1) average
Find closest (floor / ceiling)	O(n)	O(log n)	O(n)	O(log n)	O(n)
Sorted traversal	O(n log n)	O(n)	O(n log n)	O(n)	O(n log n)

Every BST operation walks one root-to-leaf path, so it costs O(h) where h is the height. The balanced column assumes h = O(log n); the self-balancing section shows how libraries guarantee it. Those libraries are the ready-made BSTs you should normally use:

Language	Ordered set	Ordered map	Implementation
C++	`std::set`, `std::multiset`	`std::map`, `std::multimap`	red-black tree
Java	`TreeSet`	`TreeMap`	red-black tree
Python	— (use `sortedcontainers.SortedList`, or `bisect` on a list)	—	no BST in the standard library
JavaScript	—	—	none built in — implement one or use a library

Operations and their cost

Operation	How	Time
`search(k)`	Go left if `k` is smaller, right if larger, stop on match or `null`	O(h)
`insert(k)`	Search for `k`; attach a new leaf where the search fell off	O(h)
`delete(k)`	Search, then one of three cases (leaf, one child, two children)	O(h)
`min()` / `max()`	Follow left / right pointers to the end	O(h)
`floor(k)` / `ceil(k)`	Search, remembering the last candidate on the way down	O(h)
`inorder()`	Left, node, right — visits keys in sorted order	O(n)

h is ⌈log₂(n + 1)⌉ for a perfectly balanced tree and n for a degenerate one, so the same code runs in O(log n) or O(n) depending only on the shape.

Insert

Every insert adds a new leaf at the point where the search ends

insert 7:   20 → smaller, go left            20
            15 → smaller, go left          /    \
            12 → smaller, go left        15      30
            null → create 7 here        /  \       \
                                      12    18      40
                                     /             /  \
                                   [7]           35    50

Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):               # insert key, keeping the BST invariant
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

def sample_bst():                    # insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    root = None
    for key in (20, 15, 30, 40, 50, 12, 18, 35, 80, 7):
        root = insert(root, key)
    return root

root = sample_bst()
print("inorder:", end=" "); inorder(root); print()
print("root:", root.key)
root = insert(root, 40)              # already present: tree unchanged
print("after insert 40 (duplicate):", end=" "); inorder(root); print()
root = insert(root, 60)              # 20 → 30 → 40 → 50 → 80 → left of 80
print("after insert 60:", end=" "); inorder(root); print()

C++

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int key) {       // insert key, keeping the BST invariant
    if (!root) return new Node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                          // duplicates are ignored
}

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

Node* sampleBST() {                       // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    Node* root = nullptr;
    for (int key : {20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
    return root;
}

int main() {
    Node* root = sampleBST();
    cout << "inorder: "; inorder(root); cout << "\n";
    cout << "root: " << root->key << "\n";
    root = insert(root, 40);              // already present: tree unchanged
    cout << "after insert 40 (duplicate): "; inorder(root); cout << "\n";
    root = insert(root, 60);              // 20 → 30 → 40 → 50 → 80 → left of 80
    cout << "after insert 60: "; inorder(root); cout << "\n";
}

Java

public class Main {
    static class Node {
        int key; Node left, right;
        Node(int k) { key = k; }
    }

    static Node insert(Node root, int key) {   // insert key, keeping the BST invariant
        if (root == null) return new Node(key);
        if (key < root.key) root.left = insert(root.left, key);
        else if (key > root.key) root.right = insert(root.right, key);
        return root;                           // duplicates are ignored
    }

    static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.key + " ");
        inorder(root.right);
    }

    static Node sampleBST() {                  // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
        Node root = null;
        for (int key : new int[]{20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
        return root;
    }

    public static void main(String[] args) {
        Node root = sampleBST();
        System.out.print("inorder: "); inorder(root); System.out.println();
        System.out.println("root: " + root.key);
        root = insert(root, 40);               // already present: tree unchanged
        System.out.print("after insert 40 (duplicate): "); inorder(root); System.out.println();
        root = insert(root, 60);               // 20 → 30 → 40 → 50 → 80 → left of 80
        System.out.print("after insert 60: "); inorder(root); System.out.println();
    }
}

JavaScript

class Node {
    constructor(key) { this.key = key; this.left = null; this.right = null; }
}

function insert(root, key) {              // insert key, keeping the BST invariant
    if (root === null) return new Node(key);
    if (key < root.key) root.left = insert(root.left, key);
    else if (key > root.key) root.right = insert(root.right, key);
    return root;                          // duplicates are ignored
}

function inorder(root) {
    if (root === null) return;
    inorder(root.left);
    process.stdout.write(root.key + " ");
    inorder(root.right);
}

function sampleBST() {                    // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    let root = null;
    for (const key of [20, 15, 30, 40, 50, 12, 18, 35, 80, 7]) root = insert(root, key);
    return root;
}

let root = sampleBST();
process.stdout.write("inorder: "); inorder(root); console.log();
console.log("root:", root.key);
root = insert(root, 40);                  // already present: tree unchanged
process.stdout.write("after insert 40 (duplicate): "); inorder(root); console.log();
root = insert(root, 60);                  // 20 → 30 → 40 → 50 → 80 → left of 80
process.stdout.write("after insert 60: "); inorder(root); console.log();

Output

inorder: 7 12 15 18 20 30 35 40 50 80
root: 20
after insert 40 (duplicate): 7 12 15 18 20 30 35 40 50 80
after insert 60: 7 12 15 18 20 30 35 40 50 60 80

Time O(h) · Space O(h) recursion stack

Iterative insert avoids the recursion stack: walk down with a parent pointer until curr is null, then hang the new node on the correct side of parent. Same O(h) time, O(1) extra space.

Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert_iter(root, key):
    node = Node(key)
    if root is None:
        return node                      # empty tree: the new node is the root
    parent, curr = None, root
    while curr is not None:              # search, remembering the parent
        if key == curr.key:
            return root                  # duplicate: nothing to do
        parent = curr
        curr = curr.left if key < curr.key else curr.right
    if key < parent.key:                 # hang the leaf on the correct side
        parent.left = node
    else:
        parent.right = node
    return root

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

root = None
for key in (20, 15, 30, 40, 50, 12, 18, 35, 80, 7):
    root = insert_iter(root, key)
print("inorder:", end=" "); inorder(root); print()
print("root:", root.key)
root = insert_iter(root, 40)
print("after insert 40 (duplicate):", end=" "); inorder(root); print()
root = insert_iter(root, 60)
print("after insert 60:", end=" "); inorder(root); print()

C++

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

Node* insertIter(Node* root, int key) {
    Node* node = new Node(key);
    if (!root) return node;                   // empty tree: the new node is the root
    Node* parent = nullptr;
    Node* curr = root;
    while (curr) {                            // search, remembering the parent
        if (key == curr->key) { delete node; return root; }   // duplicate
        parent = curr;
        curr = key < curr->key ? curr->left : curr->right;
    }
    if (key < parent->key) parent->left = node;   // hang the leaf on the correct side
    else parent->right = node;
    return root;
}

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

int main() {
    Node* root = nullptr;
    for (int key : {20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insertIter(root, key);
    cout << "inorder: "; inorder(root); cout << "\n";
    cout << "root: " << root->key << "\n";
    root = insertIter(root, 40);
    cout << "after insert 40 (duplicate): "; inorder(root); cout << "\n";
    root = insertIter(root, 60);
    cout << "after insert 60: "; inorder(root); cout << "\n";
}

Java

public class Main {
    static class Node {
        int key; Node left, right;
        Node(int k) { key = k; }
    }

    static Node insertIter(Node root, int key) {
        Node node = new Node(key);
        if (root == null) return node;             // empty tree: the new node is the root
        Node parent = null, curr = root;
        while (curr != null) {                     // search, remembering the parent
            if (key == curr.key) return root;      // duplicate: nothing to do
            parent = curr;
            curr = key < curr.key ? curr.left : curr.right;
        }
        if (key < parent.key) parent.left = node;  // hang the leaf on the correct side
        else parent.right = node;
        return root;
    }

    static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.key + " ");
        inorder(root.right);
    }

    public static void main(String[] args) {
        Node root = null;
        for (int key : new int[]{20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insertIter(root, key);
        System.out.print("inorder: "); inorder(root); System.out.println();
        System.out.println("root: " + root.key);
        root = insertIter(root, 40);
        System.out.print("after insert 40 (duplicate): "); inorder(root); System.out.println();
        root = insertIter(root, 60);
        System.out.print("after insert 60: "); inorder(root); System.out.println();
    }
}

JavaScript

class Node {
    constructor(key) { this.key = key; this.left = null; this.right = null; }
}

function insertIter(root, key) {
    const node = new Node(key);
    if (root === null) return node;           // empty tree: the new node is the root
    let parent = null, curr = root;
    while (curr !== null) {                   // search, remembering the parent
        if (key === curr.key) return root;    // duplicate: nothing to do
        parent = curr;
        curr = key < curr.key ? curr.left : curr.right;
    }
    if (key < parent.key) parent.left = node; // hang the leaf on the correct side
    else parent.right = node;
    return root;
}

function inorder(root) {
    if (root === null) return;
    inorder(root.left);
    process.stdout.write(root.key + " ");
    inorder(root.right);
}

let root = null;
for (const key of [20, 15, 30, 40, 50, 12, 18, 35, 80, 7]) root = insertIter(root, key);
process.stdout.write("inorder: "); inorder(root); console.log();
console.log("root:", root.key);
root = insertIter(root, 40);
process.stdout.write("after insert 40 (duplicate): "); inorder(root); console.log();
root = insertIter(root, 60);
process.stdout.write("after insert 60: "); inorder(root); console.log();

Output

inorder: 7 12 15 18 20 30 35 40 50 80
root: 20
after insert 40 (duplicate): 7 12 15 18 20 30 35 40 50 80
after insert 60: 7 12 15 18 20 30 35 40 50 60 80

Time O(h) · Space O(1)

Search

A search follows one path from the root

search 7:  20 → 15 → 12 → 7  ✓ found (4 comparisons)
search 25: 20 → 30 → null    ✗ 25 > 20 go right, 25 < 30 go left, nothing there

Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):               # insert key, keeping the BST invariant
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

def sample_bst():                    # insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    root = None
    for key in (20, 15, 30, 40, 50, 12, 18, 35, 80, 7):
        root = insert(root, key)
    return root

def search(root, key):                   # recursive
    if root is None:
        return False
    if key == root.key:
        return True
    if key < root.key:
        return search(root.left, key)    # only the left subtree can hold it
    return search(root.right, key)

def search_iter(root, key):              # iterative: O(1) space
    while root is not None:
        if key == root.key:
            return True
        root = root.left if key < root.key else root.right
    return False

root = sample_bst()
print("search 7:", "true" if search(root, 7) else "false")
print("search 25:", "true" if search(root, 25) else "false")
print("search 35 (iterative):", "true" if search_iter(root, 35) else "false")
print("search 100 (iterative):", "true" if search_iter(root, 100) else "false")

C++

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int key) {       // insert key, keeping the BST invariant
    if (!root) return new Node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                          // duplicates are ignored
}

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

Node* sampleBST() {                       // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    Node* root = nullptr;
    for (int key : {20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
    return root;
}

bool search(Node* root, int key) {            // recursive
    if (!root) return false;
    if (key == root->key) return true;
    if (key < root->key) return search(root->left, key);   // only the left subtree can hold it
    return search(root->right, key);
}

bool searchIter(Node* root, int key) {        // iterative: O(1) space
    while (root) {
        if (key == root->key) return true;
        root = key < root->key ? root->left : root->right;
    }
    return false;
}

int main() {
    Node* root = sampleBST();
    cout << "search 7: " << (search(root, 7) ? "true" : "false") << "\n";
    cout << "search 25: " << (search(root, 25) ? "true" : "false") << "\n";
    cout << "search 35 (iterative): " << (searchIter(root, 35) ? "true" : "false") << "\n";
    cout << "search 100 (iterative): " << (searchIter(root, 100) ? "true" : "false") << "\n";
}

Java

public class Main {
    static class Node {
        int key; Node left, right;
        Node(int k) { key = k; }
    }

    static Node insert(Node root, int key) {   // insert key, keeping the BST invariant
        if (root == null) return new Node(key);
        if (key < root.key) root.left = insert(root.left, key);
        else if (key > root.key) root.right = insert(root.right, key);
        return root;                           // duplicates are ignored
    }

    static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.key + " ");
        inorder(root.right);
    }

    static Node sampleBST() {                  // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
        Node root = null;
        for (int key : new int[]{20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
        return root;
    }

    static boolean search(Node root, int key) {        // recursive
        if (root == null) return false;
        if (key == root.key) return true;
        if (key < root.key) return search(root.left, key);   // only the left subtree can hold it
        return search(root.right, key);
    }

    static boolean searchIter(Node root, int key) {    // iterative: O(1) space
        while (root != null) {
            if (key == root.key) return true;
            root = key < root.key ? root.left : root.right;
        }
        return false;
    }

    public static void main(String[] args) {
        Node root = sampleBST();
        System.out.println("search 7: " + search(root, 7));
        System.out.println("search 25: " + search(root, 25));
        System.out.println("search 35 (iterative): " + searchIter(root, 35));
        System.out.println("search 100 (iterative): " + searchIter(root, 100));
    }
}

JavaScript

class Node {
    constructor(key) { this.key = key; this.left = null; this.right = null; }
}

function insert(root, key) {              // insert key, keeping the BST invariant
    if (root === null) return new Node(key);
    if (key < root.key) root.left = insert(root.left, key);
    else if (key > root.key) root.right = insert(root.right, key);
    return root;                          // duplicates are ignored
}

function inorder(root) {
    if (root === null) return;
    inorder(root.left);
    process.stdout.write(root.key + " ");
    inorder(root.right);
}

function sampleBST() {                    // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    let root = null;
    for (const key of [20, 15, 30, 40, 50, 12, 18, 35, 80, 7]) root = insert(root, key);
    return root;
}

function search(root, key) {                  // recursive
    if (root === null) return false;
    if (key === root.key) return true;
    if (key < root.key) return search(root.left, key);   // only the left subtree can hold it
    return search(root.right, key);
}

function searchIter(root, key) {              // iterative: O(1) space
    while (root !== null) {
        if (key === root.key) return true;
        root = key < root.key ? root.left : root.right;
    }
    return false;
}

const root = sampleBST();
console.log("search 7:", search(root, 7));
console.log("search 25:", search(root, 25));
console.log("search 35 (iterative):", searchIter(root, 35));
console.log("search 100 (iterative):", searchIter(root, 100));

Output

search 7: true
search 25: false
search 35 (iterative): true
search 100 (iterative): false

Time O(h) · Space O(h) recursive, O(1) iterative

Delete

The three cases of BST deletion

Case 1 — leaf: unlink it            Case 2 — one child: parent adopts the child
        15                                   20                 20
       /  \        delete 7                   \     delete 30     \
     12    18     ────────▶    12             30   ──────────▶    40
    /                                            \               /  \
   7                                              40           35    50

Case 3 — two children: copy the inorder successor, then delete the successor
        20          successor of 20 = min of right subtree = 35
     /      \                                   35
   15        40        delete 20             /      \
  /  \      /  \      ────────▶            15        40
12    18  35    50                        /  \         \
 /               \                      12    18        50
7                 80                     /                \
                                        7                  80

Find the node
Recurse left or right as in search; root.left = delete(root.left, key) re-attaches whatever comes back.
Leaf, or one child
Return the child (or null) to the parent — the node is bypassed.
Two children
Find succ = min(root.right), copy succ.key into root, then root.right = delete(root.right, succ.key).

Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):               # insert key, keeping the BST invariant
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

def sample_bst():                    # insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    root = None
    for key in (20, 15, 30, 40, 50, 12, 18, 35, 80, 7):
        root = insert(root, key)
    return root

def min_node(node):                      # leftmost node of a subtree
    while node.left is not None:
        node = node.left
    return node

def delete_key(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete_key(root.left, key)
    elif key > root.key:
        root.right = delete_key(root.right, key)
    else:                                # found it
        if root.left is None:            # case 1 & 2: zero or one child
            return root.right
        if root.right is None:
            return root.left
        succ = min_node(root.right)      # case 3: two children
        root.key = succ.key              # copy the inorder successor ...
        root.right = delete_key(root.right, succ.key)   # ... and remove it from the right
    return root

root = sample_bst()
root = delete_key(root, 7)
print("delete 7 (leaf):", end=" "); inorder(root); print()
root = delete_key(root, 30)
print("delete 30 (one child):", end=" "); inorder(root); print()
root = delete_key(root, 20)
print("delete 20 (two children):", end=" "); inorder(root); print()
print("new root:", root.key)

C++

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int key) {       // insert key, keeping the BST invariant
    if (!root) return new Node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                          // duplicates are ignored
}

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

Node* sampleBST() {                       // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    Node* root = nullptr;
    for (int key : {20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
    return root;
}

Node* minNode(Node* node) {                   // leftmost node of a subtree
    while (node->left) node = node->left;
    return node;
}

Node* deleteKey(Node* root, int key) {
    if (!root) return nullptr;
    if (key < root->key) root->left = deleteKey(root->left, key);
    else if (key > root->key) root->right = deleteKey(root->right, key);
    else {                                    // found it
        if (!root->left || !root->right) {    // case 1 & 2: zero or one child
            Node* child = root->left ? root->left : root->right;
            delete root;
            return child;
        }
        Node* succ = minNode(root->right);    // case 3: two children
        root->key = succ->key;                // copy the inorder successor ...
        root->right = deleteKey(root->right, succ->key);   // ... and remove it from the right
    }
    return root;
}

int main() {
    Node* root = sampleBST();
    root = deleteKey(root, 7);
    cout << "delete 7 (leaf): "; inorder(root); cout << "\n";
    root = deleteKey(root, 30);
    cout << "delete 30 (one child): "; inorder(root); cout << "\n";
    root = deleteKey(root, 20);
    cout << "delete 20 (two children): "; inorder(root); cout << "\n";
    cout << "new root: " << root->key << "\n";
}

Java

public class Main {
    static class Node {
        int key; Node left, right;
        Node(int k) { key = k; }
    }

    static Node insert(Node root, int key) {   // insert key, keeping the BST invariant
        if (root == null) return new Node(key);
        if (key < root.key) root.left = insert(root.left, key);
        else if (key > root.key) root.right = insert(root.right, key);
        return root;                           // duplicates are ignored
    }

    static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.key + " ");
        inorder(root.right);
    }

    static Node sampleBST() {                  // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
        Node root = null;
        for (int key : new int[]{20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
        return root;
    }

    static Node minNode(Node node) {               // leftmost node of a subtree
        while (node.left != null) node = node.left;
        return node;
    }

    static Node deleteKey(Node root, int key) {
        if (root == null) return null;
        if (key < root.key) root.left = deleteKey(root.left, key);
        else if (key > root.key) root.right = deleteKey(root.right, key);
        else {                                     // found it
            if (root.left == null) return root.right;   // case 1 & 2: zero or one child
            if (root.right == null) return root.left;
            Node succ = minNode(root.right);       // case 3: two children
            root.key = succ.key;                   // copy the inorder successor ...
            root.right = deleteKey(root.right, succ.key);   // ... and remove it from the right
        }
        return root;
    }

    public static void main(String[] args) {
        Node root = sampleBST();
        root = deleteKey(root, 7);
        System.out.print("delete 7 (leaf): "); inorder(root); System.out.println();
        root = deleteKey(root, 30);
        System.out.print("delete 30 (one child): "); inorder(root); System.out.println();
        root = deleteKey(root, 20);
        System.out.print("delete 20 (two children): "); inorder(root); System.out.println();
        System.out.println("new root: " + root.key);
    }
}

JavaScript

class Node {
    constructor(key) { this.key = key; this.left = null; this.right = null; }
}

function insert(root, key) {              // insert key, keeping the BST invariant
    if (root === null) return new Node(key);
    if (key < root.key) root.left = insert(root.left, key);
    else if (key > root.key) root.right = insert(root.right, key);
    return root;                          // duplicates are ignored
}

function inorder(root) {
    if (root === null) return;
    inorder(root.left);
    process.stdout.write(root.key + " ");
    inorder(root.right);
}

function sampleBST() {                    // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    let root = null;
    for (const key of [20, 15, 30, 40, 50, 12, 18, 35, 80, 7]) root = insert(root, key);
    return root;
}

function minNode(node) {                      // leftmost node of a subtree
    while (node.left !== null) node = node.left;
    return node;
}

function deleteKey(root, key) {
    if (root === null) return null;
    if (key < root.key) root.left = deleteKey(root.left, key);
    else if (key > root.key) root.right = deleteKey(root.right, key);
    else {                                    // found it
        if (root.left === null) return root.right;    // case 1 & 2: zero or one child
        if (root.right === null) return root.left;
        const succ = minNode(root.right);     // case 3: two children
        root.key = succ.key;                  // copy the inorder successor ...
        root.right = deleteKey(root.right, succ.key);   // ... and remove it from the right
    }
    return root;
}

let root = sampleBST();
root = deleteKey(root, 7);
process.stdout.write("delete 7 (leaf): "); inorder(root); console.log();
root = deleteKey(root, 30);
process.stdout.write("delete 30 (one child): "); inorder(root); console.log();
root = deleteKey(root, 20);
process.stdout.write("delete 20 (two children): "); inorder(root); console.log();
console.log("new root:", root.key);

Output

delete 7 (leaf): 12 15 18 20 30 35 40 50 80
delete 30 (one child): 12 15 18 20 35 40 50 80
delete 20 (two children): 12 15 18 35 40 50 80
new root: 35

Time O(h) · Space O(h)

Floor in a BST

key == x
Return this node — nothing can be closer.
key > x
Too big; the floor must be in the left subtree: root = root.left.
key < x
A valid candidate; a larger one may exist to the right: res = root; root = root.right.

The candidate is updated only when we step right

floor(14):  20 > 14  → go left           candidate: —
            15 > 14  → go left           candidate: —
            12 < 14  → remember, go right  candidate: 12
            null     → answer 12

Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):               # insert key, keeping the BST invariant
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

def sample_bst():                    # insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    root = None
    for key in (20, 15, 30, 40, 50, 12, 18, 35, 80, 7):
        root = insert(root, key)
    return root

def floor(root, x):
    res = None
    while root is not None:
        if root.key == x:
            return root                  # exact match
        if root.key > x:
            root = root.left             # too big: look left
        else:
            res = root                   # candidate; a larger one may be on the right
            root = root.right
    return res

root = sample_bst()
for x in (14, 1, 20, 100):
    node = floor(root, x)
    print(f"floor({x}) =", node.key if node else "none")

C++

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int key) {       // insert key, keeping the BST invariant
    if (!root) return new Node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                          // duplicates are ignored
}

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

Node* sampleBST() {                       // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    Node* root = nullptr;
    for (int key : {20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
    return root;
}

Node* floorNode(Node* root, int x) {
    Node* res = nullptr;
    while (root) {
        if (root->key == x) return root;      // exact match
        if (root->key > x) root = root->left; // too big: look left
        else { res = root; root = root->right; }   // candidate; a larger one may be on the right
    }
    return res;
}

int main() {
    Node* root = sampleBST();
    for (int x : {14, 1, 20, 100}) {
        Node* node = floorNode(root, x);
        cout << "floor(" << x << ") = ";
        if (node) cout << node->key << "\n"; else cout << "none\n";
    }
}

Java

public class Main {
    static class Node {
        int key; Node left, right;
        Node(int k) { key = k; }
    }

    static Node insert(Node root, int key) {   // insert key, keeping the BST invariant
        if (root == null) return new Node(key);
        if (key < root.key) root.left = insert(root.left, key);
        else if (key > root.key) root.right = insert(root.right, key);
        return root;                           // duplicates are ignored
    }

    static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.key + " ");
        inorder(root.right);
    }

    static Node sampleBST() {                  // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
        Node root = null;
        for (int key : new int[]{20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
        return root;
    }

    static Node floor(Node root, int x) {
        Node res = null;
        while (root != null) {
            if (root.key == x) return root;            // exact match
            if (root.key > x) root = root.left;        // too big: look left
            else { res = root; root = root.right; }    // candidate; a larger one may be on the right
        }
        return res;
    }

    public static void main(String[] args) {
        Node root = sampleBST();
        for (int x : new int[]{14, 1, 20, 100}) {
            Node node = floor(root, x);
            System.out.println("floor(" + x + ") = " + (node != null ? String.valueOf(node.key) : "none"));
        }
    }
}

JavaScript

class Node {
    constructor(key) { this.key = key; this.left = null; this.right = null; }
}

function insert(root, key) {              // insert key, keeping the BST invariant
    if (root === null) return new Node(key);
    if (key < root.key) root.left = insert(root.left, key);
    else if (key > root.key) root.right = insert(root.right, key);
    return root;                          // duplicates are ignored
}

function inorder(root) {
    if (root === null) return;
    inorder(root.left);
    process.stdout.write(root.key + " ");
    inorder(root.right);
}

function sampleBST() {                    // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    let root = null;
    for (const key of [20, 15, 30, 40, 50, 12, 18, 35, 80, 7]) root = insert(root, key);
    return root;
}

function floor(root, x) {
    let res = null;
    while (root !== null) {
        if (root.key === x) return root;          // exact match
        if (root.key > x) root = root.left;       // too big: look left
        else { res = root; root = root.right; }   // candidate; a larger one may be on the right
    }
    return res;
}

const root = sampleBST();
for (const x of [14, 1, 20, 100]) {
    const node = floor(root, x);
    console.log(`floor(${x}) =`, node ? node.key : "none");
}

Output

floor(14) = 12
floor(1) = none
floor(20) = 20
floor(100) = 80

Time O(h) · Space O(1)

Ceiling in a BST

key == x
Return this node.
key < x
Too small; the ceiling must be on the right: root = root.right.
key > x
A valid candidate; a smaller one may exist to the left: res = root; root = root.left.

Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

def insert(root, key):               # insert key, keeping the BST invariant
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored

def inorder(root):
    if root:
        inorder(root.left)
        print(root.key, end=" ")
        inorder(root.right)

def sample_bst():                    # insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    root = None
    for key in (20, 15, 30, 40, 50, 12, 18, 35, 80, 7):
        root = insert(root, key)
    return root

def ceil(root, x):
    res = None
    while root is not None:
        if root.key == x:
            return root                  # exact match
        if root.key < x:
            root = root.right            # too small: look right
        else:
            res = root                   # candidate; a smaller one may be on the left
            root = root.left
    return res

root = sample_bst()
for x in (21, 5, 7, 81):
    node = ceil(root, x)
    print(f"ceil({x}) =", node.key if node else "none")

C++

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
    Node(int k) : key(k), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int key) {       // insert key, keeping the BST invariant
    if (!root) return new Node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    return root;                          // duplicates are ignored
}

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

Node* sampleBST() {                       // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    Node* root = nullptr;
    for (int key : {20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
    return root;
}

Node* ceilNode(Node* root, int x) {
    Node* res = nullptr;
    while (root) {
        if (root->key == x) return root;       // exact match
        if (root->key < x) root = root->right; // too small: look right
        else { res = root; root = root->left; }   // candidate; a smaller one may be on the left
    }
    return res;
}

int main() {
    Node* root = sampleBST();
    for (int x : {21, 5, 7, 81}) {
        Node* node = ceilNode(root, x);
        cout << "ceil(" << x << ") = ";
        if (node) cout << node->key << "\n"; else cout << "none\n";
    }
}

Java

public class Main {
    static class Node {
        int key; Node left, right;
        Node(int k) { key = k; }
    }

    static Node insert(Node root, int key) {   // insert key, keeping the BST invariant
        if (root == null) return new Node(key);
        if (key < root.key) root.left = insert(root.left, key);
        else if (key > root.key) root.right = insert(root.right, key);
        return root;                           // duplicates are ignored
    }

    static void inorder(Node root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.key + " ");
        inorder(root.right);
    }

    static Node sampleBST() {                  // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
        Node root = null;
        for (int key : new int[]{20, 15, 30, 40, 50, 12, 18, 35, 80, 7}) root = insert(root, key);
        return root;
    }

    static Node ceil(Node root, int x) {
        Node res = null;
        while (root != null) {
            if (root.key == x) return root;            // exact match
            if (root.key < x) root = root.right;       // too small: look right
            else { res = root; root = root.left; }     // candidate; a smaller one may be on the left
        }
        return res;
    }

    public static void main(String[] args) {
        Node root = sampleBST();
        for (int x : new int[]{21, 5, 7, 81}) {
            Node node = ceil(root, x);
            System.out.println("ceil(" + x + ") = " + (node != null ? String.valueOf(node.key) : "none"));
        }
    }
}

JavaScript

class Node {
    constructor(key) { this.key = key; this.left = null; this.right = null; }
}

function insert(root, key) {              // insert key, keeping the BST invariant
    if (root === null) return new Node(key);
    if (key < root.key) root.left = insert(root.left, key);
    else if (key > root.key) root.right = insert(root.right, key);
    return root;                          // duplicates are ignored
}

function inorder(root) {
    if (root === null) return;
    inorder(root.left);
    process.stdout.write(root.key + " ");
    inorder(root.right);
}

function sampleBST() {                    // insert 20, 15, 30, 40, 50, 12, 18, 35, 80, 7
    let root = null;
    for (const key of [20, 15, 30, 40, 50, 12, 18, 35, 80, 7]) root = insert(root, key);
    return root;
}

function ceil(root, x) {
    let res = null;
    while (root !== null) {
        if (root.key === x) return root;          // exact match
        if (root.key < x) root = root.right;      // too small: look right
        else { res = root; root = root.left; }    // candidate; a smaller one may be on the left
    }
    return res;
}

const root = sampleBST();
for (const x of [21, 5, 7, 81]) {
    const node = ceil(root, x);
    console.log(`ceil(${x}) =`, node ? node.key : "none");
}

Output

ceil(21) = 30
ceil(5) = 7
ceil(7) = 7
ceil(81) = none

Time O(h) · Space O(1)

Self-balancing BSTs: why and how

The same set of keys can make BSTs of very different heights — it depends only on the insertion order. The operations above are O(h), so the whole point of balancing is to keep h = O(log n) no matter what order the keys arrive in.

Same keys, two heights: every operation is O(n) on the left and O(log n) on the right

insert 7, 10, 11, 15, 30, 35, 40          insert 15, 10, 35, 7, 11, 30, 40
(sorted order → height 7)                 (balanced → height 3)

  7                                                  15
   \                                               /    \
    10                                           10      35
      \                                         /  \    /  \
       11                                      7    11 30   40
         \
          15
            \
             30
               \
                35
                  \
                   40

If all keys were known in advance we could build the perfectly balanced tree directly (insert the middle of the sorted keys, then recurse on each half). With random insertions and deletions we cannot — so a self-balancing tree restructures itself after every insert or delete that makes it lopsided.

Inserting 100, 200, 300 produces a chain; one rotation turns it back into a balanced tree

insert 100          insert 200          insert 300           restructure
                                                             (rotate left at 100)
   100                 100                 100                     200
                          \                   \                   /   \
                           200                 200              100     300
                                                  \
                                                   300

The restructuring tool is the rotation: a local change of two or three pointers that moves a subtree one level up on one side and one level down on the other without breaking the BST order — the inorder sequence T1 y T2 x T3 is the same before and after.

A rotation re-hangs T2 on the other node and is O(1)

        P                                            P
        |                                            |
        x            Right rotation at x             y
      /   \         ─────────────────────▶         /   \
     y     T3                                     T1    x
    / \             ◀─────────────────────             / \
  T1   T2            Left rotation at y              T2   T3

inorder before:  T1  y  T2  x  T3          inorder after:  T1  y  T2  x  T3   (unchanged)

Rotation	Pointer changes	Effect
Right rotation at `x`	`y = x.left; x.left = y.right; y.right = x`; `P` now points at `y`	Left subtree gets one level shorter, right subtree one level taller
Left rotation at `y`	`x = y.right; y.right = x.left; x.left = y`; `P` now points at `x`	The mirror image

The two famous self-balancing BSTs differ only in what counts as balanced and therefore in when they rotate: the AVL tree (strict, by height) and the red-black tree (looser, by colouring).

AVL tree

Named after Adelson-Velsky and Landis (1962). The height condition guarantees h ≤ 1.44 log₂ n, so every operation is O(log n). Each node stores its height so the balance factor is O(1) to compute.

Normal BST insert
Walk down and attach the new leaf as usual.
Walk back up updating heights
The recursion returns through every ancestor of the new node; recompute height = 1 + max(hL, hR) at each.
Find the first unbalanced ancestor
The lowest node with |bf| > 1. Only ancestors can be unbalanced, and fixing the lowest one fixes everything above it for an insert.
Rotate according to one of four cases
Decided by which grandchild subtree the new key went into.

Case	Where the key went	Fix	Rotations
Left-Left (LL)	Left child's left subtree (`bf > 1` and `key < left.key`)	Right rotation at the unbalanced node	1 (single)
Right-Right (RR)	Right child's right subtree (`bf < −1` and `key > right.key`)	Left rotation at the unbalanced node	1 (single)
Left-Right (LR)	Left child's right subtree (`bf > 1` and `key > left.key`)	Left rotation at the left child, then right rotation at the node	2 (double)
Right-Left (RL)	Right child's left subtree (`bf < −1` and `key < right.key`)	Right rotation at the right child, then left rotation at the node	2 (double)

The LL case: the chain 20 → 15 → 5 becomes a balanced tree rooted at 15 (from the notes)

insert 20         insert 15         insert 5             Left-Left at 20:
                                                         right rotation
   20                20                20                      15
                    /                 /                      /    \
                  15                15                      5      20
                                   /
                                  5          bf(20) = 2 - 0 = +2 → unbalanced

The double-rotation cases: the first rotation turns them into LL / RR, the second fixes the balance

Left-Right at 30 (insert 30, 10, 20):      Right-Left at 10 (insert 10, 30, 20):

    30            30            20            10           10            20
   /    left     /    right    /  \            \   right    \   left    /  \
 10   rotate   20   rotate   10    30          30  rotate   20  rotate 10    30
   \  at 10    /     at 30                     /   at 30      \   at 10
    20       10                              20                30

Python

class Node:
    def __init__(self, key):
        self.key = key
        self.left = self.right = None
        self.height = 1                  # a new node is a leaf (node-counting convention)

def height(node):
    return node.height if node else 0

def balance(node):
    return height(node.left) - height(node.right)

def update(node):
    node.height = 1 + max(height(node.left), height(node.right))

def rotate_right(x):                     # x's left child y becomes the subtree root
    y = x.left
    x.left = y.right                     # T2 moves across
    y.right = x
    update(x); update(y)                 # x first: it is now below y
    return y

def rotate_left(x):                      # mirror image
    y = x.right
    x.right = y.left
    y.left = x
    update(x); update(y)
    return y

def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    else:
        return root                      # duplicate
    update(root)                         # on the way back up
    bf = balance(root)
    if bf > 1 and key < root.left.key:   # Left-Left
        return rotate_right(root)
    if bf < -1 and key > root.right.key: # Right-Right
        return rotate_left(root)
    if bf > 1 and key > root.left.key:   # Left-Right
        root.left = rotate_left(root.left)
        return rotate_right(root)
    if bf < -1 and key < root.right.key: # Right-Left
        root.right = rotate_right(root.right)
        return rotate_left(root)
    return root

def preorder(root):
    if root:
        print(root.key, end=" ")
        preorder(root.left)
        preorder(root.right)

def build(keys):
    root = None
    for k in keys:
        root = insert(root, k)
    return root

for label, keys in (("LL", (20, 15, 5)), ("RR", (100, 200, 300)), ("LR", (30, 10, 20)), ("RL", (10, 30, 20))):
    root = build(keys)
    print(label, " ".join(map(str, keys)) + ": root", str(root.key) + ", preorder", end=" ")
    preorder(root); print()
root = build((20, 15, 30, 40, 50, 12, 18, 35, 80, 7))
print("sample keys: preorder", end=" "); preorder(root); print()
print("height:", root.height)

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

struct Node {
    int key, height = 1;                 // a new node is a leaf (node-counting convention)
    Node *left = nullptr, *right = nullptr;
    Node(int k) : key(k) {}
};

int height(Node* n) { return n ? n->height : 0; }
int balance(Node* n) { return height(n->left) - height(n->right); }
void update(Node* n) { n->height = 1 + max(height(n->left), height(n->right)); }

Node* rotateRight(Node* x) {             // x's left child y becomes the subtree root
    Node* y = x->left;
    x->left = y->right;                  // T2 moves across
    y->right = x;
    update(x); update(y);                // x first: it is now below y
    return y;
}

Node* rotateLeft(Node* x) {              // mirror image
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    update(x); update(y);
    return y;
}

Node* insert(Node* root, int key) {
    if (!root) return new Node(key);
    if (key < root->key) root->left = insert(root->left, key);
    else if (key > root->key) root->right = insert(root->right, key);
    else return root;                                   // duplicate
    update(root);                                       // on the way back up
    int bf = balance(root);
    if (bf > 1 && key < root->left->key) return rotateRight(root);       // Left-Left
    if (bf < -1 && key > root->right->key) return rotateLeft(root);      // Right-Right
    if (bf > 1 && key > root->left->key) {                               // Left-Right
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }
    if (bf < -1 && key < root->right->key) {                             // Right-Left
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }
    return root;
}

void preorder(Node* root) {
    if (!root) return;
    cout << root->key << " ";
    preorder(root->left);
    preorder(root->right);
}

Node* build(const vector<int>& keys) {
    Node* root = nullptr;
    for (int k : keys) root = insert(root, k);
    return root;
}

int main() {
    vector<pair<string, vector<int>>> cases = {
        {"LL", {20, 15, 5}}, {"RR", {100, 200, 300}}, {"LR", {30, 10, 20}}, {"RL", {10, 30, 20}}};
    for (auto& [label, keys] : cases) {
        Node* root = build(keys);
        cout << label;
        for (int k : keys) cout << " " << k;
        cout << ": root " << root->key << ", preorder ";
        preorder(root); cout << "\n";
    }
    Node* root = build({20, 15, 30, 40, 50, 12, 18, 35, 80, 7});
    cout << "sample keys: preorder "; preorder(root); cout << "\n";
    cout << "height: " << root->height << "\n";
}

Java

public class Main {
    static class Node {
        int key, height = 1;             // a new node is a leaf (node-counting convention)
        Node left, right;
        Node(int k) { key = k; }
    }

    static int height(Node n) { return n == null ? 0 : n.height; }
    static int balance(Node n) { return height(n.left) - height(n.right); }
    static void update(Node n) { n.height = 1 + Math.max(height(n.left), height(n.right)); }

    static Node rotateRight(Node x) {    // x's left child y becomes the subtree root
        Node y = x.left;
        x.left = y.right;                // T2 moves across
        y.right = x;
        update(x); update(y);            // x first: it is now below y
        return y;
    }

    static Node rotateLeft(Node x) {     // mirror image
        Node y = x.right;
        x.right = y.left;
        y.left = x;
        update(x); update(y);
        return y;
    }

    static Node insert(Node root, int key) {
        if (root == null) return new Node(key);
        if (key < root.key) root.left = insert(root.left, key);
        else if (key > root.key) root.right = insert(root.right, key);
        else return root;                                   // duplicate
        update(root);                                       // on the way back up
        int bf = balance(root);
        if (bf > 1 && key < root.left.key) return rotateRight(root);       // Left-Left
        if (bf < -1 && key > root.right.key) return rotateLeft(root);      // Right-Right
        if (bf > 1 && key > root.left.key) {                               // Left-Right
            root.left = rotateLeft(root.left);
            return rotateRight(root);
        }
        if (bf < -1 && key < root.right.key) {                             // Right-Left
            root.right = rotateRight(root.right);
            return rotateLeft(root);
        }
        return root;
    }

    static void preorder(Node root) {
        if (root == null) return;
        System.out.print(root.key + " ");
        preorder(root.left);
        preorder(root.right);
    }

    static Node build(int[] keys) {
        Node root = null;
        for (int k : keys) root = insert(root, k);
        return root;
    }

    public static void main(String[] args) {
        String[] labels = {"LL", "RR", "LR", "RL"};
        int[][] cases = {{20, 15, 5}, {100, 200, 300}, {30, 10, 20}, {10, 30, 20}};
        for (int i = 0; i < 4; i++) {
            Node root = build(cases[i]);
            StringBuilder sb = new StringBuilder(labels[i]);
            for (int k : cases[i]) sb.append(" ").append(k);
            System.out.print(sb + ": root " + root.key + ", preorder ");
            preorder(root); System.out.println();
        }
        Node root = build(new int[]{20, 15, 30, 40, 50, 12, 18, 35, 80, 7});
        System.out.print("sample keys: preorder "); preorder(root); System.out.println();
        System.out.println("height: " + root.height);
    }
}

JavaScript

class Node {
    constructor(key) { this.key = key; this.left = null; this.right = null; this.height = 1; }
}                                        // a new node is a leaf (node-counting convention)

const height = (n) => n === null ? 0 : n.height;
const balance = (n) => height(n.left) - height(n.right);
const update = (n) => { n.height = 1 + Math.max(height(n.left), height(n.right)); };

function rotateRight(x) {                // x's left child y becomes the subtree root
    const y = x.left;
    x.left = y.right;                    // T2 moves across
    y.right = x;
    update(x); update(y);                // x first: it is now below y
    return y;
}

function rotateLeft(x) {                 // mirror image
    const y = x.right;
    x.right = y.left;
    y.left = x;
    update(x); update(y);
    return y;
}

function insert(root, key) {
    if (root === null) return new Node(key);
    if (key < root.key) root.left = insert(root.left, key);
    else if (key > root.key) root.right = insert(root.right, key);
    else return root;                                   // duplicate
    update(root);                                       // on the way back up
    const bf = balance(root);
    if (bf > 1 && key < root.left.key) return rotateRight(root);       // Left-Left
    if (bf < -1 && key > root.right.key) return rotateLeft(root);      // Right-Right
    if (bf > 1 && key > root.left.key) {                               // Left-Right
        root.left = rotateLeft(root.left);
        return rotateRight(root);
    }
    if (bf < -1 && key < root.right.key) {                             // Right-Left
        root.right = rotateRight(root.right);
        return rotateLeft(root);
    }
    return root;
}

function preorder(root) {
    if (root === null) return;
    process.stdout.write(root.key + " ");
    preorder(root.left);
    preorder(root.right);
}

const build = (keys) => keys.reduce((root, k) => insert(root, k), null);

for (const [label, keys] of [["LL", [20, 15, 5]], ["RR", [100, 200, 300]], ["LR", [30, 10, 20]], ["RL", [10, 30, 20]]]) {
    const root = build(keys);
    process.stdout.write(`${label} ${keys.join(" ")}: root ${root.key}, preorder `);
    preorder(root); console.log();
}
const root = build([20, 15, 30, 40, 50, 12, 18, 35, 80, 7]);
process.stdout.write("sample keys: preorder "); preorder(root); console.log();
console.log("height:", root.height);

Output

LL 20 15 5: root 15, preorder 15 5 20
RR 100 200 300: root 200, preorder 200 100 300
LR 30 10 20: root 20, preorder 20 10 30
RL 10 30 20: root 20, preorder 20 10 30
sample keys: preorder 20 15 12 7 18 40 30 35 50 80
height: 4

Time O(log n) per insert — one path down plus at most two rotations · Space O(log n) recursion stack

Red-black tree

Every node is either red or black.
The root is always black.
No two consecutive reds: a red node has only black children (a red node's parent is black).
Every path from a node down to its descendant null leaves has the same number of black nodes (the black height).

A valid red-black tree holding the sample keys — the colouring the notes drew violated rule 4, so it is redrawn here

                 20 (B)
              /         \
         15 (B)           40 (B)
        /     \          /      \
   12 (B)    18 (B)   30 (B)    50 (B)
   /                      \         \
7 (R)                    35 (R)    80 (R)

black nodes on every root → null path: 3   (20-15-12, 20-15-18, 20-40-30, 20-40-50, …)
longest path: 20-15-12-7-null (4 nodes)   shortest: 20-15-18-null (3 nodes)  → ≤ 2×

Why the rules bound the height. Rule 4 says every path has the same number b of black nodes; rule 3 says reds cannot be adjacent, so a path has at most b reds squeezed between its blacks. The shortest possible path is all black (b nodes); the longest alternates (2b nodes). Hence no path is more than twice as long as any other — the statement at the end of the notes — and since a tree with b blacks on every path has at least 2^b − 1 nodes, b ≤ log₂(n + 1) and h ≤ 2 log₂(n + 1).

Insertion colours the new node red (that never breaks rule 4), then fixes any red-red violation by recolouring and at most two rotations. Deletion is more involved but also needs at most three rotations. The code is long and rarely asked in interviews; the properties and the comparison below are.

	AVL tree	Red-black tree
Balance rule	`\|hL − hR\| ≤ 1` at every node (strict)	Colour rules; longest path ≤ 2 × shortest (loose)
Height bound	`≤ 1.44 log₂ n` — shorter	`≤ 2 log₂ n` — a bit taller
Search	Faster (shorter tree)	Slightly slower
Insert	≤ 2 rotations, but more frequent rebalancing	≤ 2 rotations, mostly just recolouring
Delete	Up to `O(log n)` rotations	≤ 3 rotations
Extra data per node	Height (an int) or balance factor	1 bit (the colour)
Best for	Lookup-heavy data that changes rarely (databases, dictionaries)	Frequent inserts/deletes
Used in	Some database indexes, Windows kernel	`std::map`/`set`, Java `TreeMap`/`TreeSet`, Linux scheduler (CFS) and memory manager

Applications of a BST

Interview Q&A

How do you check whether a binary tree is a BST?

What is the worst-case complexity of search in a BST, and how do you avoid it?

How do you delete a node that has two children?

How do you find the kth smallest element in a BST?

AVL or red-black — which would you choose?

How do a BST and a hash table compare?