Trees: Binary Trees, BST, AVL and B-Trees For students.

A tree is a data structure of nodes connected by edges, organised as a hierarchy like a family tree. Every tree has one root at the top, and every other node has exactly one parent above it and zero or more children below it. Nodes with no children are called leaves. Unlike real trees, computer-science trees are drawn upside down, with the root at the top.

Trees matter because hierarchical data is everywhere: file systems, org charts, website menus, and the HTML of every web page. Special trees — binary search trees, AVL trees, and B-trees — store sorted data so cleverly that searching a million records takes about 20 steps instead of a million.

Key Concepts

• Root: the top node, the only one with no parent. Leaf: a node with no children.
• Height: edges on the longest root-to-leaf path (a single node has height 0). Depth: a node's distance from the root.
• Binary tree: each node has at most two children, left and right.
• Binary search tree (BST): left subtree holds smaller values, right subtree larger values — this ordering enables fast search.
• AVL tree: a BST that stays balanced — subtree heights differ by at most 1 at every node — using rotations after updates.
• B-tree: a balanced tree where each node holds many keys and children, designed for disks and databases.

Formulas

• Maximum nodes: a binary tree with h levels holds at most 2^h − 1 nodes; a 4-level perfect tree has 15 nodes.
• Minimum height: n nodes need height at least floor(log2 n). One million nodes need height ≥ 19, since 2^20 = 10,48,576.
• BST search: O(h) where h is height — O(log n) when balanced, degrading to O(n) as a straight chain.
• AVL balance factor: height(left) − height(right) must stay in {−1, 0, 1}; violations are fixed by rotations.
• B-tree: all leaves at the same depth, so search, insert, and delete are all O(log n).

Worked Example

Insert 50, 30, 70, 20, 40, 60, 80 into an empty BST. 50 becomes the root. 30 goes left of 50, 70 goes right. 20 goes left of 30; 40 goes right of 30. 60 goes left of 70; 80 goes right of 70. The result has 3 levels and 7 nodes — and 2^3 − 1 = 7, so it is perfect. Searching for 60 now takes 3 comparisons (50, 70, 60) instead of scanning all 7 values. In a balanced tree of a million values the same search would take about 20 comparisons — the power of keeping height logarithmic.

Common Misconceptions

• "A binary tree and a BST are the same." Wrong. A binary tree only limits children to two; a BST adds the ordering rule that makes searching fast.
• "AVL trees are always faster than plain BSTs." Not for insert-heavy workloads — AVL's strict balancing gives the fastest searches but slower insertions.
• "B-trees are only for databases." Mostly, but the wide-node idea is also used in file systems and anywhere data lives on slow storage.

Real-World Applications

• Binary trees: expression parsing in compilers, Huffman coding for compression.
• BSTs: in-memory indexes, symbol tables, ordered maps.
• AVL trees: indexes that must stay fast under constant inserts and deletes.
• B-trees: the index structure behind MySQL, PostgreSQL, and file systems like NTFS.

A binary tree gives the shape, a BST adds order, an AVL tree guarantees balance, and a B-tree scales that balance to disks holding billions of records. Master these four, and you understand the machinery inside every database on earth.