What is a Tree?
A tree is a non-linear, hierarchical data structure used to represent data with a parent-child relationship. Unlike arrays or linked lists which store data linearly, trees organize information across multiple levels, making them highly efficient for searching, sorting, and managing hierarchical systems like file directories or DOM structures.
Core Terminology
○ Root
│
┌───────┴───────┐
│ │
○ A ○ B ← Siblings: A & B share same parent
│ │
┌───┴───┐ ┌───┴───┐
│ │ │ │
○ C ○ D ○ E ○ F ← Children of A: C, D
(leaf) (leaf) (leaf) ← C, E, F are Leaves (no children)
Subtree at A = {A, C, D}RootTopmost node — no parent
NodeBasic unit: data + links to children
EdgeLink connecting two nodes
ParentNode above — owns the edge to child
ChildNode below — edge comes from parent
SiblingNodes sharing same parent
LeafNode with no children — dead end
SubtreeA node + all its descendants
Structural Properties
DepthNumber of edges from the root to a specific node. Root has depth 0.
HeightNumber of edges on the longest path from a node to a leaf.
DegreeThe total number of children a specific node has.
LevelDepth of a node + 1. Root is at level 1.
Pros and Cons
Advantages
- ›Hierarchical — natural fit for file systems, org charts, DOM
- ›Efficient searching — O(log n) with balanced trees
- ›Dynamic size — no fixed capacity like arrays
- ›Natural recursion — tree operations are naturally recursive
Disadvantages
- ›No O(1) operations — all are O(log n) or worse
- ›Unbalanced trees degrade to O(n)
- ›Complex to implement — requires pointer management
- ›Extra memory overhead for child pointers