The Family Tree Analogy
A family tree shows relationships:
- One person at the top (ancestor/root)
- Each person can have children below them
- Each person typically has one parent in the tree (except the root)
- No circular relationships (you can't be your own grandparent!)
Trees in computer science work the same way - they store data in a hierarchical structure with parent-child relationships.
Tree Structure
CEO ← Root (no parent)
/ | \
VP VP VP ← Level 1
/| / \ \
D D D D D ← Level 2 (Leaves)
Terminology
Root: Top node (CEO) - no parent
Parent: Node above (VP is parent of D)
Child: Node below (D is child of VP)
Siblings: Nodes with same parent
Leaf: Node with no children
Edge: Connection between parent and child
Height: Longest path from root to any leaf
Depth: Distance from root to a specific node
Subtree: A node and all its descendants
Tree vs Graph vs Linked List
Tree:
A
/|\
B C D Hierarchical, no cycles, one parent
Graph:
A---B
| \ / | Connections anywhere, can have cycles |
| X | |
| / \ | |
C---D
Linked List:
A → B → C → D Linear, typically one path
Trees are special graphs: connected, no cycles, one path between any two nodes.
Why Trees?
Fast Operations
Sorted array: Search O(log n), Insert O(n)
Linked list: Search O(n), Insert O(1)
Balanced tree: Search O(log n), Insert O(log n)
Trees can offer a useful middle ground.
Natural Hierarchies
File systems:
/
├── home/
│ ├── user/
│ │ ├── documents/
│ │ └── pictures/
│ └── admin/
└── var/
HTML DOM:
<html>
<head>...</head>
<body>
<div>
<p>...</p>
</div>
</body>
</html>
Types of Trees
Binary Tree
Each node has at most 2 children:
1
/ \
2 3
/ \
4 5
Binary Search Tree (BST)
Binary tree with ordering: left < parent < right:
5
/ \
3 7
/ \ / \
1 4 6 9
N-ary Tree
Each node can have any number of children:
1
/ | \
2 3 4
/|
5 6 7
Balanced Trees
Height is often kept to O(log n) in self-balancing trees, which helps keep operations fast:
AVL Tree: Heights of subtrees differ by at most 1
Red-Black Tree: Uses color properties to maintain balance
B-Tree: Used in databases, multiple keys per node
Tree Traversals
Depth-First Traversals
1
/ \
2 3
/ \
4 5
Preorder (Root, Left, Right): 1, 2, 4, 5, 3
Inorder (Left, Root, Right): 4, 2, 5, 1, 3
Postorder (Left, Right, Root): 4, 5, 2, 3, 1
Breadth-First (Level Order)
Level 0: 1
Level 1: 2, 3
Level 2: 4, 5
Order: 1, 2, 3, 4, 5
When to Use Each
| Traversal | Use Case |
|---|---|
| Preorder | Copy tree, serialize |
| Inorder | Get sorted order (BST) |
| Postorder | Delete tree, evaluate expressions |
| Level order | Print by level, find depth |
Common Tree Operations
Find Height
1
/ \
2 3
/
4
Height = 2 (longest path: 1 → 2 → 4)
Algorithm: max(leftHeight, rightHeight) + 1
Count Nodes
Total nodes = 1 + countLeft + countRight
Find Diameter
Longest path between any two nodes
(may or may not pass through root)
Real-World Applications
File Systems
C:\
├── Program Files\
│ ├── App1\
│ └── App2\
└── Users\
└── Documents\
Organization Charts
CEO → VPs → Directors → Managers → Engineers
HTML/XML DOM
Browser parses HTML into a tree.
JavaScript traverses it to manipulate the page.
Databases (B-Trees)
Database indexes use B-trees for efficient queries.
Each node can have many children, reducing height.
Abstract Syntax Trees (AST)
Expression: 2 + 3 * 4
+
/ \
2 *
/ \
3 4
Tree vs Other Structures
| Structure | Search | Insert | Ordered | Hierarchy |
|---|---|---|---|---|
| Array | O(n) | O(1) | No | No |
| Sorted Array | O(log n) | O(n) | Yes | No |
| Linked List | O(n) | O(1) | No | No |
| BST (balanced) | O(log n) | O(log n) | Yes | Yes |
| Hash Table | O(1) | O(1) | No | No |
Common Mistakes
1. Forgetting Base Cases
Trees are recursive - usually handle empty/null nodes.
2. Confusing Height and Depth
Height: from node down to deepest leaf. Depth: from root down to node.
3. Ignoring Balance
Unbalanced trees degrade to linked lists: O(n) operations!
4. Off-by-One in Height
Is a single node height 0 or 1? Be consistent with your definition.
FAQ
Q: When should I use a tree vs a graph?
Tree: hierarchical data with clear parent-child relationships. Graph: complex connections, cycles, no clear hierarchy.
Q: Tree vs hash table?
Hash table: O(1) lookup but no ordering. Tree: O(log n) lookup but maintains order.
Q: What's a forest?
Multiple trees - a collection of disconnected trees.
Q: How do I balance a tree?
Use self-balancing variants: AVL, Red-Black, B-Tree.
Summary
A tree is a hierarchical data structure with parent-child relationships and no cycles.
Key Takeaways:
- One root, each node has one parent (except root)
- Leaves have no children
- Binary tree: max 2 children per node
- BST: left < parent < right
- Traversals: preorder, inorder, postorder, level-order
- Balanced trees typically support O(log n) operations
- Used everywhere: file systems, DOM, databases, parsers
Trees are fundamental - from file systems to databases to syntax analysis!
Related Concepts
Leave a Comment
Comments (0)
Be the first to comment on this concept.
Comments are approved automatically.