Introduction to Trees

[!NOTE] This module explores the core principles of Introduction to Trees, deriving solutions from first principles and hardware constraints to build world-class, production-ready expertise.

1. The Hook: Hierarchical Reality

Lists, Stacks, and Queues are linear. They represent a sequence of events. However, the world we build for is hierarchical.

• File Systems: Root → Folders → Files.
• Web Browsers: The DOM (Document Object Model).
• Organizational Charts: CEO → VPs → Managers.

A Tree is the most powerful nonlinear data structure for representing these relationships. It allows us to move from O(N) “street scanning” to O(log N) “branch jumping.”

War Story: The “Too Many Friends” Search In the early days of social networks, finding a specific user in a flat list of millions of records resulted in massive database timeouts. You cannot search a linear array of 1 Billion users in real-time. By structuring the relationships hierarchically, searching became a game of “branch jumping.” A balanced tree structure turns 1,000,000,000 checks into just ~30 jumps (log₂ 1,000,000,000 ≈ 30).

---

2. The 4 Pillars of Tree Mastery

Pillar	Focus	Why it matters
1. Intuition	Recursive Nature	Seeing a tree as a node + two subtrees.
2. Rigor	Height Induction	Proving properties like max nodes or min height.
3. Hardware	Pointer Chasing	Understanding the cache locality cost of branching.
4. Patterns	Traversal Profiles	Choosing DFS vs BFS based on tree shape.

---

3. Anatomy of a Binary Tree

A Binary Tree is a tree where every node has at most 2 children (Left and Right).

• Root: The top node (no parent).
• Leaf: A node with no children.
• Edge: The link between two nodes.
• Height: Max edges from node to leaf (Root height = max depth).
• Depth: Edges from root to node.

The Recursive Definition

A Tree is:

1. Empty (null), OR
2. A Node (Data) + Left Tree + Right Tree.

---

4. The Mathematical Anchor: Height Induction

How many nodes can a binary tree of height h hold?

The Proof by Induction

Proposition: A binary tree of height h has at most 2^h+1 - 1 nodes.

1. Base Case (h=0): A tree with only the root has 2⁰⁺¹ - 1 = 2¹ - 1 = 1 node. True.
2. Inductive Step: Assume a tree of height h-1 has at most N_h-1 = 2^(h-1)+1 - 1 = 2^h - 1 nodes.
3. A tree of height h is a root plus two subtrees of max height h-1.
4. Total nodes N_h = 1 + N_left + N_right
5. N_h ≤ 1 + (2^h - 1) + (2^h - 1) = 2 · 2^h - 1 = 2^h+1 - 1.
6. Conclusion: By induction, the formula holds for all h ≥ 0.

[!IMPORTANT] This relationship is fundamental to Big-O. If a tree is balanced, its height h ≈ \log₂ N. This is why searching becomes lightning fast.

---

5. Interactive: Tree Builder

Click to add nodes. See how the structure grows.

Tree Empty.

6. Implementation

A Tree Node is just like a Linked List Node, but with two pointers.

Java

public class TreeNode {
  int val;
  TreeNode left;
  TreeNode right;

  public TreeNode(int val) {
    this.val = val;
  }
}

Go

type TreeNode struct {
  Val   int
  Left  *TreeNode
  Right *TreeNode
}

7. Hardware Reality: Pointers Galore

Just like Linked Lists, Trees are scattered in memory.

• Traversing a tree involves jumping from address 0x100 to 0x900 to 0x200.
• Cache Misses: High. CPU caches (L1/L2) fetch memory in contiguous chunks. Because tree nodes are dynamically allocated and scattered, jumping between them often results in cache misses, making trees slower than contiguous Arrays for raw iteration.
• Memory Overhead: Each node carries data + 2 pointers (16 bytes on 64-bit systems).

When to use them? If you only need to store and iterate sequentially, use an Array to benefit from spatial locality. If you need dynamic O(log N) inserts, deletes, and searches without massive memory reallocation, use a Tree.

In the next chapter, we’ll see how sorting the tree makes it powerful.