Types of Tree

A tree's shape — how many children a node may have, whether levels must be packed left-to-right, whether subtree heights must stay within 1 of each other — is the invariant a specific algorithm depends on: a heap needs completeness to stay array-indexable, a BST needs balance to guarantee O(log n) search. "Type of tree" is shorthand for "which structural invariant this data structure or algorithm assumes and maintains."

Convention used throughout this page: height h = number of edges on the longest root-to-leaf path (a single node has h = 0). This is the standard CS convention and is applied consistently below, including to the skewed case.

Recognize the pattern

• "Array-backed tree" / "heap" / "priority queue" → expects a complete binary tree — only shape safely indexable with 2i+1, 2i+2.
• "Balanced BST" or a claim of guaranteed O(log n) → expects a height-balanced tree (AVL / Red-Black); a plain BST degrades to a list on sorted input.
• "Decision tree", "expression/parse tree", "strict binary operator tree" → expects a full (proper) binary tree: every node has 0 or 2 children, never 1.
• "File system", "trie", "B-tree", "org chart", "HTML DOM" → expects a multi-way (n-ary) tree, branching factor unbounded or >2.

Brute force vs. optimal

Brute force: use one generic, unconstrained binary tree for every job (BST, priority queue emulation, hierarchy storage). Node placement follows insertion order only, so a search or a min-extract can degrade to O(n) — e.g. inserting 1,2,3,4,5 into a BST with no rebalancing produces a right-only chain of height 4 (edges), not log2(5)≈2.3.

Optimal: choose the tree type whose invariant matches the operation you need, and enforce that invariant on every insert/delete: complete for array-backed heaps (O(log n) sift-up/down, O(1) extra space, no pointers needed), balanced for BSTs (rotations after insert/delete cap height at O(log n)), full for parse/expression/Huffman trees (guarantees every internal node is a clean binary combinator, simplifying recursive evaluation), multi-way when branching factor legitimately exceeds 2 (tries collapse shared prefixes, B-trees minimize disk seeks by fanning out per node).

Complexity, derived

Height from node count (the core argument). Height h is the number of edges on the longest root-to-leaf path, applied identically in every case below. For a binary tree with n nodes:

• Worst case (skewed / unconstrained BST): each level holds exactly 1 node, so a chain of n nodes has n−1 edges → h = n−1 = O(n). Search/insert/delete walks up to h edges → O(n) time.
• Complete tree: a tree of height h has levels 0..h (that's h+1 levels); level i holds up to 2^i nodes, and completeness requires every level except possibly the last to be full. So the minimum node count for height h is: fill levels 0..h−1 completely (2^0+2^1+…+2^(h−1) = 2^h−1 nodes) plus at least 1 node on level h → n ≥ 2^h−1+1 = 2^h. That gives 2^h ≤ n, i.e. h ≤ log2 n; because the tree is packed left-to-right with no wasted levels, h is exactly ⌊log2 n⌋. Heap push/pop walks at most h levels → O(log n) time, O(1) extra space (array-backed, no child pointers stored).
• Balanced tree (AVL, |height diff| ≤ 1 at every node): minimum node count for height h follows N(h) = N(h−1) + N(h−2) + 1 — a Fibonacci-like recurrence — which solves to N(h) = O(φ^h), so h = O(log n). Search/insert/delete: O(log n) time; rebalancing after insert touches O(log n) ancestors → still O(log n) time, O(1) extra space beyond the recursion stack.
• Multi-way tree, branching factor b, n nodes: height h ≈ log_b(n). More children per node → shorter tree but more comparisons per node (up to b−1 per level) — total work per search is O(b · log_b n), which is why B-trees pick b to match disk-block size (minimize seeks, accept more in-block comparisons, cheap since they're in RAM/cache).

Space for all four types is O(n) nodes; the difference is per-node overhead (array slot for complete/heap vs. two pointers for BST/AVL vs. a child-list/array of size b for multi-way).

Traced example: is this array a valid (min-)heap, i.e. complete + heap-ordered?

Array: [3, 9, 5, 12, 8, 15, 7], 0-indexed, children of i at 2i+1, 2i+2, n = 7.

Completeness, checked the same way the reference code below checks it: isComplete walks the tree breadth-first and fails as soon as it sees a real node after a null child. This array's implicit tree has every index 0..6 occupied and no index beyond 6 — equivalent to a BFS that enqueues seven non-null nodes and then only nulls, never a non-null node after a gap. So running isComplete on the tree this array encodes returns true: structurally complete. Separately, scanning parent/child pairs above finds index 4 (value 8, parent 9) violating min-heap order. Conclusion: isComplete only certifies shape; it says nothing about the parent≤child value check done in the table — a valid heap needs both to pass, and here only completeness does.

Pitfalls

• Assuming "balanced" means "complete" (or vice versa) — they are independent properties; a tree can be height-balanced but not array-packable, or complete but heavily right-heavy in value distribution.
• Confusing full (0-or-2 children) with complete (levels packed left-to-right) and with perfect (all leaves at same depth, all internal nodes have 2 children) — three distinct terms interviewers use precisely.
• Building a BST from sorted/near-sorted input without self-balancing and expecting O(log n) — you get O(n) height instead.
• Using array-index math (2i+1) on a tree that is not guaranteed complete — silently wastes memory or misindexes children.
• Forgetting that heap-order (parent ≤ children for min-heap) is a separate invariant from completeness — a complete tree is not automatically a valid heap (see worked example).
• Mixing height conventions (edges vs. node count) mid-derivation — always fix one convention (this page uses edges) before comparing Big-O across tree types.

When to use / when not

Which balanced tree, and why — AVL vs. Red-Black

"Balanced BST" is not one structure; the two standard choices trade rotation cost against how tight the height stays. Both are height-balanced (h = Θ(log n)), but the constants and rebalance work differ:

AVL is rigidly balanced, so its lookups are the tightest, but it pays with more rotations on every mutation. Red-black lets the tree grow up to twice as tall, which lets it rotate less on insert/delete. That is exactly why general-purpose library maps that must stay fast across arbitrary insert/delete/lookup mixes pick red-black: Java's TreeMap and C++'s std::map are red-black trees. Rule of thumb: AVL for lookup-dominated data, red-black for balanced read/write. Both fix the plain-BST degeneracy (sorted input → O(n) chain) that motivates balancing in the first place; the AVL minimum-node recurrence N(h) = N(h−1) + N(h−2) + 1 is Fibonacci-like, which is where the ≈1.44 log₂ n bound comes from.

Reference: checking completeness (Java, BFS)

Standalone snippet — TreeNode is defined inline so this compiles without relying on a definition elsewhere on the page:

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

boolean isComplete(TreeNode root) {
    java.util.Queue<TreeNode> q = new java.util.LinkedList<>();
    q.add(root);
    boolean seenNull = false;
    while (!q.isEmpty()) {
        TreeNode node = q.poll();
        if (node == null) {
            seenNull = true;
        } else {
            if (seenNull) return false; // non-null after a gap -> not complete
            q.add(node.left);
            q.add(node.right);
        }
    }
    return true;
}

Run mentally on the traced array [3,9,5,12,8,15,7] built as a tree (node i's children are array indices 2i+1, 2i+2, absent past index 6): the queue drains all seven non-null nodes before hitting any null, so seenNull never turns true before a real node → returns true, matching the completeness conclusion reached by inspection above.

Takeaways

• Tree "type" = which shape/value invariant is enforced; the invariant, not the name, is what buys you a complexity guarantee.
• Complete enables array indexing (heaps); balanced enables guaranteed O(log n) search (AVL/RB); full guarantees clean binary recursion (parse trees); multi-way trades pointer simplicity for shorter height at higher branching.
• Derive height from node count per type, using one consistent convention (edges) throughout — skewed h=n−1=O(n), complete h=⌊log2 n⌋ from n≥2^h, balanced h=O(log n), multi-way h=O(log_b n) — rather than memorizing Big-O labels.
• Shape and value-order are separate axes: a tree can satisfy one without the other (complete array that isn't heap-ordered).

Recall: Given a complete binary tree stored as an array of size n, why is its height guaranteed to be Θ(log n) regardless of insertion order, while a plain BST's height on the same n keys can range from log n to n?

Synthesized from standard DSA references (CLRS trees/heaps chapters, standard interview-prep binary tree taxonomies) and the original source page's binary/full/complete/balanced/multi-way definitions.