Binary Search Tree & AVL Tree

What is a Binary Search Tree (BST)?

A Binary Search Tree is a hierarchical data structure where each node has at most two children. It maintains a specific ordering property that makes searching efficient.

• BST Property: For any node, all values in its left subtree are smaller, and all values in its right subtree are larger
• Average Case: O(log n) for search, insert, delete
• Worst Case: O(n) when tree becomes a linked list (skewed)
• Use Cases: Implementing sets, maps, priority queues, database indexing

What is an AVL Tree?

An AVL tree is a self-balancing BST invented by Adelson-Velsky and Landis. It automatically rebalances itself after insertions and deletions to maintain optimal height.

• Balance Factor: Height(left subtree) - Height(right subtree)
• AVL Property: Balance factor must be -1, 0, or 1 for every node
• Guaranteed: O(log n) for all operations
• Trade-off: Slightly slower inserts/deletes due to rotations, but faster searches in worst case

Time Complexity Comparison

Operation	BST Average	BST Worst	AVL (All)
Search	O(log n)	O(n)	O(log n)
Insert	O(log n)	O(n)	O(log n)
Delete	O(log n)	O(n)	O(log n)
Space	O(n)		O(n)

AVL Rotations Explained

When a node becomes unbalanced (balance factor outside -1 to 1), AVL trees perform rotations to restore balance:

Left Rotation (RR Case)

Used when right subtree is too tall (balance factor = -2). The right child becomes the new root.

Right Rotation (LL Case)

Used when left subtree is too tall (balance factor = +2). The left child becomes the new root.

Left-Right Rotation (LR Case)

Double rotation: Left rotate left child, then right rotate root. Used when left subtree is right-heavy.

Right-Left Rotation (RL Case)

Double rotation: Right rotate right child, then left rotate root. Used when right subtree is left-heavy.

Tree Traversals

• Inorder (Left → Root → Right): Visits nodes in sorted order. Used for getting sorted data.
• Preorder (Root → Left → Right): Visits root first. Used for copying trees or prefix expressions.
• Postorder (Left → Right → Root): Visits root last. Used for deleting trees or postfix expressions.

When to Use Which?

• Use BST when: Data is relatively random, simplicity is preferred, or memory is constrained
• Use AVL when: Guaranteed performance is critical, data may be sorted/sequential, or frequent searches occur
• Consider Red-Black Tree: If insertions/deletions are more frequent than searches (fewer rotations)