Node, edge, root, parent/child, siblings

Subtree, leaf (external) node, internal node

Degree (of node/tree)

Depth/level, height

Path, distance

Ordered vs unordered trees

Each node has at most 2 children (left/right)

Strict/Full Binary Tree: every node has 0 or 2 children

Perfect Binary Tree: all internal nodes have 2 children; all leaves at same level

Complete Binary Tree: all levels full except possibly last, filled left to right

Balanced vs Skewed

Binary tree variants mainly differ by shape constraints that bound height and impact performance.

Binary Search Tree (BST): left < root < right (by key)

Heap (Binary Heap): min-heap / max-heap (parent ordered vs children)

Self-Balancing BSTs: AVL, Red-Black (keep height logarithmic)

Tries (Prefix Trees): character-based branching for strings

Node object with pointers: children (and optionally parent)

Binary tree node: left, right

0-based indexing: i → left 2i+1, right 2i+2, parent ⌊(i-1)/2⌋

Efficient for heaps; wasteful for sparse/skewed trees

Use pointers for irregular shapes; use arrays when the tree is near-complete and index math is valuable.

Preorder (Root-Left-Right)

Inorder (Left-Root-Right)

Postorder (Left-Right-Root)

Implementation Styles

Level-order traversal (queue)

Uses: shortest path in unweighted tree, printing by levels, completeness checks

Morris Traversal (binary tree): inorder with O(1) extra space by temporary threading

Euler Tour Technique: supports subtree queries, entry/exit times

General tree: often O(n) without ordering

BST: average O(log n), worst O(n) if unbalanced

Average O(log n); rebalancing in AVL/RB adds rotations

Often O(n) via traversal

File systems, organization charts, XML/HTML DOM

Menus, category taxonomies

BST-based dictionaries/sets/maps

Database indexing (conceptually tree-based; e.g., B-trees in practice)

Heaps for priority queues (OS scheduling, Dijkstra/A*)

Parse trees / Abstract Syntax Trees (AST)

Expression trees for evaluation/optimization

Tries for autocomplete, spell-check, routing by prefix

Decision trees, game trees (minimax)

Routing tables (trie-like), spanning trees (conceptual)

Array for complete-ish trees; pointers for sparse/irregular trees

Use self-balancing trees when worst-case matters

Match traversal order to task (sorted output, deletion, level processing)