Trees: Hierarchical Data

In the previous chapter we covered hash tables.

Now we explore a different style of organization: hierarchy.

---

What Is a Tree?

A tree is a structure of nodes connected in parent-child relationships.

Key terms:

• root: top node
• child: node below another node
• leaf: node with no children

graph TD
  A[Root]
  A --> B[Child 1]
  A --> C[Child 2]
  B --> D[Leaf]
  C --> E[Leaf]

---

Binary Trees

A binary tree is a tree where each node has at most two children.

This structure is a foundation for several important variants used in searching and balancing.

---

Why Trees Are Useful

Trees are strong when data is naturally hierarchical or when ordered organization is needed.

Common uses:

• file systems
• syntax trees in compilers
• database and storage indexes
• search-oriented structures

---

Traversal Idea

You process trees by traversal strategies, such as:

• depth-first
• breadth-first

Different traversals serve different algorithm goals.

---

Trees vs Hash Tables

Hash tables are great for exact-key lookup.

Trees are often better when order and range operations matter.

This is another DSA tradeoff pattern.

---

Key Ideas to Remember

• Trees represent hierarchical relationships.
• Root, child, and leaf are core concepts.
• Binary trees are a common foundational form.
• Trees are useful for indexing and structured data models.
• They complement, rather than replace, hash-based structures.

---

What Comes Next

Trees model hierarchy.

Next we study a more general structure for arbitrary relationships:

graphs.