Binary Search Trees

• The defining properties of a Binary Search Tree (BST)
• How to insert, search, and delete nodes efficiently
• Why in-order traversal produces sorted output
• The difference between balanced and unbalanced BSTs
• Time complexity: average O(log n) vs worst-case O(n)
• The basics of AVL trees and self-balancing

BST Property

A BST is a binary tree where every node satisfies:

Left subtree values < Node value < Right subtree values

This holds recursively for every node in the tree.

        50
       /  \
      30   70
     / \   / \
    20  40 60  80

Core Operations

Insert Algorithm

1. Start at root.
2. If new value < current node → go left; else → go right.
3. Repeat until an empty spot is found; insert there.

Search Algorithm

1. Start at root.
2. If value == current node → found.
3. If value < current → search left subtree.
4. If value > current → search right subtree.
5. If null is reached → not found.

Delete Algorithm (three cases)

In-Order Traversal → Sorted Output

Traversal order: Left → Root → Right

For the tree above: 20 → 30 → 40 → 50 → 60 → 70 → 80

This property makes BSTs useful for sorting and range queries.

Balanced vs Unbalanced BST

Skewed tree example — inserting 10, 20, 30, 40 in order produces a linked list, not a tree.

AVL Trees (Self-Balancing BST)

An AVL tree maintains the balance factor at every node:

Balance Factor = Height(Left subtree) − Height(Right subtree)

Allowed values: −1, 0, or +1. If violated after insert/delete, the tree is rotated to restore balance.

AVL trees guarantee O(log n) for all operations even in the worst case.

1. A BST contains values 15, 10, 20, 8, 12, 17, 25. Write the result of an in-order traversal.

2. What is the worst-case time complexity for searching in a BST, and when does this worst case occur?

3. You need to delete node 20 from the BST below. Node 20 has left child 17 and right child 25, and 25 has left child 22. What value replaces 20, and why?

4. Explain why inserting data that is already sorted into a standard BST is inefficient.

5. What condition does an AVL tree enforce that a standard BST does not, and how does it maintain that condition after an insertion?