Day 6 — Binary Trees and BSTs

Today we move from linear data (arrays, lists, stacks, queues) to hierarchical data. Trees are the structure behind file systems, syntax parsers, expression evaluators, decision processes — anything where one thing branches into many.

We’ll focus on the workhorse of the family: the binary tree (every node has at most two children) and its sorted variant, the Binary Search Tree (BST).

What you’ll learn today

• The vocabulary of trees — root, leaf, depth, height, ancestor, descendant — and the difference between depth and height (a real interview gotcha)
• The family of tree types: full, complete, perfect, balanced, BST, AVL, Red-Black, heap, trie, segment tree, B-tree — what each is for and why
• The four traversals every interview asks about: inorder, preorder, postorder, level-order — recursive and iterative versions
• BST operations: search, insert, and the surprisingly tricky delete-with-two-children case
• Ten practice problems covering every major tree pattern — recursion templates, fused traversals, BFS layers, divide-and-conquer

Roadmap

1. Introduction — the tree vocabulary, why we care about hierarchical data, and the first interactive visualizations.
2. Tree Types — the whole family: full, complete, perfect, balanced, BST, AVL, Red-Black, heap, trie, segment tree, B-tree. What each shape unlocks.
3. Traversals — inorder, preorder, postorder, level-order. Recursive and iterative versions for each, plus the application table that tells you which to reach for.
4. BST Operations — search, insert, and the three cases of delete (no children, one child, two children — the last one needs the in-order successor trick).
5. Basic Questions — warm-up problems: traversals, height, count, max value.
6. Practice Questions — ten classic interview problems covering every tree pattern you’ll see.

Up next: Heaps on Day 7 — which are also binary trees, with one extra property that turns them into priority queues.