When modeling relationships between entities, one of the most fundamental questions is: how many entities can participate on each side of the relationship?

This is the question of cardinality—and it's the precise mathematical distinction that separates trees from graphs.

Consider these scenarios:

Scenario A: Employee to Manager

• Each employee reports to exactly one manager
• Each manager can have multiple direct reports
• This is a one-to-many relationship (one manager to many employees)

Scenario B: Student to Course

• Each student can enroll in multiple courses
• Each course can have multiple students
• This is a many-to-many relationship

The structural implications are profound. Scenario A forms a tree. Scenario B forms a graph. Understanding cardinality is understanding which data structure your problem requires.

Cardinality describes the numerical constraints on relationships between entities. It answers: "How many X can be associated with how many Y?"

There are four fundamental cardinality patterns:

The key insight:

One-to-one and one-to-many relationships can be represented with simpler structures (arrays, trees). Many-to-many relationships fundamentally require more complex structures (graphs) because the constraints are looser.

Note on perspective:

One-to-many and many-to-one are the same relationship viewed from different sides. "One manager has many employees" (1:N from manager's view) is equivalent to "Each employee has one manager" (N:1 from employee's view). The data structure implications are the same—this relationship forms a tree.

One-to-many relationships are the defining characteristic of tree structures. Let's examine this relationship in depth.

In a one-to-many relationship, each element in set A can be associated with multiple elements in set B, but each element in set B is associated with exactly one element in set A.

Visualizing the constraint:

Set A ("Parents")     Set B ("Children")
     ┌───┐           ┌───┐
     │ A │───────────│ 1 │
     └───┘           ├───┤
       │             │ 2 │
       └─────────────├───┤
                     │ 3 │
     ┌───┐           └───┘
     │ B │───────────┌───┐
     └───┘           │ 4 │
       │             ├───┤
       └─────────────│ 5 │
                     └───┘

Notice: each element in Set B (1, 2, 3, 4, 5) points back to exactly one element in Set A. This is the single-parent constraint that defines trees.

Real-world one-to-many relationships:

In every case, the 'many' side belongs to exactly one 'one'—this is what makes these relationships tree-compatible.

Let's prove mathematically why one-to-many relationships must form tree structures.

Theorem: Any connected structure where each element (except one distinguished "root") has exactly one "parent" forms a tree.

Proof sketch:

1. Start with any element X. Follow the parent relationship: X → parent(X) → parent(parent(X)) → ...

2. This chain must terminate. Since each step moves to a unique parent, and we have finite elements, the chain cannot cycle (it would need to revisit an element, but that element can't have two parents). It must end at an element with no parent: the root.

3. The path is unique. If there were two paths from X to the root, X would need two parents at the branching point. Contradiction.

4. The structure is connected. Every element can reach the root through its unique parent chain.

5. The structure is acyclic. Proven in step 2.

6. Therefore it's a tree. A connected, acyclic structure with a designated root is precisely the definition of a tree. ∎

Implications for data structure design:

1. Pointer structure: In a tree implementation, each node needs only one "parent" pointer (to traverse up) and a collection of "children" pointers (to traverse down). Many implementations omit parent pointers entirely.

2. Memory efficiency: With n-1 edges for n nodes, trees use O(n) memory for relationships—the minimum possible for a connected structure.

3. Algorithmic simplicity: The unique path property means we never need to track "visited" nodes during traversal—we can't revisit a node by following parent-child relationships.

4. Recursive decomposition: Every subtree is itself a tree. This enables elegant recursive algorithms: solve the problem for the root, recursively solve for children, combine results.

Many-to-many relationships are fundamentally more general than one-to-many. They require graph structures because trees cannot represent them faithfully.

In a many-to-many relationship, each element in set A can be associated with multiple elements in set B, AND each element in set B can be associated with multiple elements in set A.

Visualizing the complexity:

Set A ("Students")    Set B ("Courses")
     ┌───┐           ┌───────┐
     │ S1│───────────│ Math  │
     └───┘╲         ╱└───────┘
       │   ╲       ╱    │
       │    ╲     ╱     │
       │     ╲   ╱      │
     ┌───┐    ╲ ╱     ┌───────┐
     │ S2│─────X──────│Science│
     └───┘    ╱ ╲     └───────┘
       │     ╱   ╲      │
       │    ╱     ╲     │
       │   ╱       ╲    │
     ┌───┐╱         ╲┌───────┐
     │ S3│───────────│History│
     └───┘           └───────┘

S1 takes Math and Science. S2 takes all three. S3 takes Science and History. Math has S1 and S2. Science has all three students. This web of connections cannot be represented as a tree.

Real-world many-to-many relationships:

Notice how both sides of each relationship can have multiple associations. This fundamentally requires graph representation.

Let's understand why trees are fundamentally incapable of representing many-to-many relationships faithfully.

The Tree Attempt:

Suppose we try to represent students-courses as a tree with courses as parents and students as children:

        Courses (root level)
       /    |    \
    Math  Science  History
    /  \   /  \  \   /  \
   S1  S2 S1  S2  S3 S2  S3

Problem: S1 appears twice (under Math and Science). S2 appears three times. We've duplicated nodes, violating the tree property that each node exists exactly once.

The fundamental incompatibility:

Trees require the single-parent property. Many-to-many relationships explicitly violate it. These are mathematically incompatible requirements.

The graph solution:

Graphs impose no parent constraints. Each node can connect to any number of other nodes. The students-courses relationship becomes:

Graph representation:
- Nodes: {S1, S2, S3, Math, Science, History}
- Edges: {(S1,Math), (S1,Science), (S2,Math), (S2,Science), 
         (S2,History), (S3,Science), (S3,History)}

No duplication. No structural lies. The representation matches the reality.

Bipartite graph perspective:

Many-to-many relationships between two distinct sets naturally form bipartite graphs—graphs where nodes can be divided into two sets such that every edge connects a node from one set to a node from the other.

This is precisely the students-courses structure:

• Set A: Students
• Set B: Courses
• Every edge connects a student to a course (never student-student or course-course)

Bipartite graphs have special properties and algorithms (maximum matching, for example) that apply specifically to many-to-many relationships between distinct entity types.

Let's place all cardinality patterns on a spectrum from most constrained to least constrained:

Most Constrained → Least Constrained:

1:1          1:N / N:1         N:M
One-to-One → One-to-Many → Many-to-Many
   │              │              │
   ▼              ▼              ▼
Simplest     Trees/Forests    Graphs
structures   (hierarchical)   (network)

The expressiveness trade-off:

Less constrained structures are more expressive—they can represent more relationship patterns. But they're also more complex to work with:

Choose the tightest constraint that fits your data. If your relationships are truly 1:N, don't use a graph—you'll pay for expressiveness you don't need. If they're truly N:M, don't try to force a tree—you'll create a structural lie.

Real-world systems often have more nuanced cardinality patterns than pure 1:N or N:M. Understanding these patterns helps you make more precise structural decisions.

Pattern 1: Bounded Many-to-Many

Sometimes 'many' has practical limits. A student might take at most 6 courses per semester. A course might have at most 200 students. These bounded relationships are still N:M structurally, but the bounds affect storage and algorithm choices.

Pattern 2: Sparse Many-to-Many

In a social network with 1 million users, each user might have ~100-1000 friends on average. That's 10⁸ - 10⁹ edges, far less than the 10¹² potential edges. Sparse N:M relationships favor adjacency lists over adjacency matrices.

Pattern 3: Mostly One-to-Many with Exceptions

Most employees have one manager, but the CEO has none, and some employees might have two (matrix organization). This is 'almost 1:N' but the exceptions break tree structure. You might model it as a DAG (multiple parents allowed) or a graph.

Pattern 4: Self-Referential Relationships

An entity relates to entities of its own type:

Self-referential relationships are common and can have any cardinality. Friendship is N:M. Reporting structure is N:1. Each maps to different data structures.

Pattern 5: Temporal Cardinality Changes

Relationships might have different cardinalities at different times:

• An employee has one manager now, but may have had different managers before
• Modeling current state: 1:N tree
• Modeling history: N:M graph with time attributes

The right structure depends on what questions you need to answer.

Developing the skill to quickly identify cardinality from problem descriptions is essential for efficient data structure selection.

Signal words for One-to-Many (1:N):

Signal words for Many-to-Many (N:M):

Practice analysis:

For each scenario, identify the cardinality:

1. "Each book has one ISBN, and each ISBN identifies one book."

   • Answer: 1:1 — Use a map/dictionary

2. "A folder contains files and other folders. Each file/folder is in exactly one parent folder."

   • Answer: 1:N — Use a tree (file system)

3. "Actors appear in movies. Movies have casts of actors."

   • Answer: N:M — Use a graph (or database junction table)

4. "Each function can call multiple functions. Functions can be called by multiple callers."

   • Answer: N:M — Use a graph (call graph)

5. "Each city is in one country. Countries contain many cities."

   • Answer: 1:N — Use a tree (geographic hierarchy)

6. "Nodes in a network can ping any other node. Connections are bidirectional."

   • Answer: N:M — Use an undirected graph

We've developed a rigorous understanding of how relationship cardinality determines data structure choices. Let's consolidate the essential insights:

What's next:

With a solid understanding of non-linear relationships and cardinality, we're ready to explore concrete examples of non-linear data structures. The next page examines trees, graphs, heaps, and tries—the four major non-linear structures you'll encounter throughout your DSA journey and engineering career.