Why Graphs Exist and What Trees Cannot Model in DSA Typescript - Challenge Your Understanding

Challenge - 5 Problems

🧠 Conceptual

intermediate

Why can't trees model all relationships?

Which of the following scenarios cannot be accurately represented by a tree structure?

A A family tree showing parent-child relationships

B A company's organizational chart with one manager per employee

C A social network where people can be friends with multiple others

D A file system directory with folders and subfolders

💡 Hint

Think about whether each node can have multiple parents or connections.

Trees have a strict hierarchy where each node has only one parent. Social networks allow multiple connections between nodes, which trees cannot represent.

❓ Predict Output

intermediate

Output of graph adjacency list vs tree adjacency list

Given the following adjacency lists, which one represents a graph that cannot be a tree?

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C']
};

DSA Typescript

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C']
};

console.log(graph);

A {"A":["B","C"],"B":["A"],"C":["A"],"D":["B"]}

B {"A":["B","C"],"B":["D"],"C":["A"],"D":[]}

C {"A":["B"],"B":["C"],"C":["D"],"D":[]}

D {"A":["B","C"],"B":["A","D"],"C":["A","D"],"D":["B","C"]}

💡 Hint

Look for cycles or multiple parents in the adjacency list.

Option D shows nodes connected in a cycle (A-B-D-C-A), which trees cannot have.

🔧 Debug

advanced

Identify the error in tree vs graph edge representation

Which option shows an incorrect edge representation for a tree structure?

Edges:
A - B
B - C
C - A

A Edges form a cycle: A-B, B-C, C-A, which is invalid for trees

B Edges form a linear chain: A-B, B-C, which is valid for trees

C Edges form a star: A-B, A-C, which is valid for trees

D Edges form disconnected nodes: A-B, C-D, which is valid for trees

💡 Hint

Trees cannot have cycles.

Option A forms a cycle, which violates the tree property of having no cycles.

🚀 Application

advanced

Choosing graph over tree for modeling

You want to model a city's road network where intersections connect multiple roads in various ways. Which data structure is best?

A Tree, because roads branch out from a central point

B Graph, because intersections can connect multiple roads forming cycles

C Linked list, because roads are linear

D Stack, because roads can be traversed in order

💡 Hint

Think about whether the structure allows cycles and multiple connections.

Graphs allow cycles and multiple connections, which fits road networks better than trees.

🧠 Conceptual

expert

Why graphs are necessary beyond trees

Which property of graphs makes them necessary to model relationships that trees cannot?

A Graphs allow multiple parents per node and cycles, unlike trees

B Graphs enforce a strict hierarchy with no cycles

C Graphs only allow one path between nodes

D Graphs are always directed and acyclic

💡 Hint

Consider the flexibility of connections in graphs vs trees.

Graphs can have cycles and nodes with multiple parents, which trees cannot, making graphs more flexible for complex relationships.