Part V — Tree Structures

Trees dominate coding interviews. Across thousands of interview reports from major tech companies, tree problems appear in roughly 40% of all coding rounds. The reason is straightforward: trees test recursion, pointer manipulation, algorithmic thinking, and edge-case handling — all in a single problem. If you walk into an interview without rock-solid tree fundamentals, you leave points on the table.

Core Terminology

Every tree conversation starts with vocabulary. Get these definitions into muscle memory:

Node: A unit containing a value (or key) and references to child nodes.
Root: The topmost node with no parent. Every tree has exactly one root.
Leaf: A node with zero children. These sit at the “bottom” of the tree.
Edge: The connection between a parent node and a child node.
Height: The number of edges on the longest path from a node down to a leaf. A leaf has height 0. The tree’s height equals the root’s height.
Depth: The number of edges from the root down to a given node. The root has depth 0.
Subtree: Any node together with all its descendants forms a subtree.
Degree: The number of children a node has.
Balance Factor: The difference between the height of the left subtree and the right subtree. A balanced tree keeps this factor within a bounded range at every node.

These terms appear in problem descriptions, constraints, and interviewer follow-up questions. Misusing them signals a shaky foundation.

Binary Tree Variants

Binary trees — where each node has at most two children — are the backbone of tree interview problems. Three subclasses come up repeatedly:

Variant	Definition	Key Property
Full Binary Tree	Every node has 0 or 2 children	No node has exactly one child
Complete Binary Tree	All levels are fully filled except possibly the last, which fills left-to-right	Used by heaps
Perfect Binary Tree	All internal nodes have 2 children and all leaves are at the same depth	Contains exactly 2^(h+1) − 1 nodes for height h

Interviewers test whether you can identify which variant a problem requires. Heaps demand completeness. Balanced BSTs demand bounded height. Segment trees are perfect binary trees over a fixed range.

The Four Traversal Types

Traversals form the operational backbone for nearly every tree algorithm. Four traversal orders exist, each serving distinct use cases:

Preorder (Root → Left → Right): Visit the current node before its children. Creates a serialization that captures tree structure. Used in copying trees and prefix expression evaluation.

Inorder (Left → Root → Right): Visit the left subtree, then the current node, then the right subtree. On a Binary Search Tree, this produces elements in sorted ascending order. The most common traversal in BST problems.

Postorder (Left → Right → Root): Visit children before the parent. Used when you need to process or delete children before the parent — think garbage collection, directory size computation, or postfix expressions.

Level-Order (Breadth-First): Visit nodes level by level, left to right. Uses a queue instead of recursion. Essential for problems involving tree width, minimum depth, zigzag traversal, and right-side view.

Every tree problem you encounter reduces to one or more of these traversals with added logic at the visit step.

Balanced vs. Unbalanced

A balanced tree keeps its height at O(log n), where n is the number of nodes. An unbalanced (skewed) tree degenerates into a linked list with height O(n). This distinction controls the time complexity of search, insert, and delete operations:

Balanced (AVL, Red-Black): All operations run in O(log n).
Unbalanced (degenerate BST): All operations degrade to O(n).

Interviewers often ask: “What happens when this tree is skewed?” The answer reveals whether you understand the gap between best-case and worst-case performance.

What This Part Covers

This part walks through seven sub-chapters, each building on the last:

Binary Trees — Traversals (recursive and iterative), construction from traversals, classic problems like LCA and diameter.
Binary Search Trees — The BST property, search/insert/delete, validation, and ordered-data problems.
AVL Trees — Self-balancing through rotations, the balance factor, and how strict balancing guarantees O(log n).
Red-Black Trees — Color-based balancing rules, insertion fixup, and why Java’s TreeMap and HashMap rely on them.
Heaps and Priority Queues — Array-based complete binary trees, heap operations, and the PriorityQueue API.
Tries (Prefix Trees) — Character-by-character search, autocomplete, and dictionary problems.
Segment Trees and Binary Indexed Trees — Range queries and point updates for competitive programming and advanced interviews.

Each sub-chapter provides full Java 25 implementations, annotated with the reasoning behind every design choice. You will write code, trace through examples, and internalize the patterns that transfer across problems.

Trees reward deep understanding over memorization. A candidate who truly grasps recursive decomposition and traversal-order selection solves novel tree problems in real time. That is the skill this part builds.