Computer Science · 10th Grade · Advanced Data Structures and Management · Weeks 10-18

Introduction to Trees and Graphs

Students are introduced to non-linear data structures like trees and graphs, understanding their basic properties and uses.

• Common Core State Standards
• CSTA: 3A-AP-14

About This Topic

Trees and graphs are non-linear data structures that model relationships between data in ways that lists and arrays cannot. A tree organizes data hierarchically -- each node has at most one parent and potentially many children -- making it ideal for representing file systems, organizational charts, HTML document structure, and decision logic. Binary trees, where each node has at most two children, are a foundational type that leads directly to efficient search and sort algorithms. This topic aligns with CSTA standard 3A-AP-14.

Graphs generalize trees by removing the parent-child restriction: any node can connect to any other node, and connections can be directional or bidirectional. Social networks, road maps, airline route networks, and the internet itself are all graph structures. Students who understand graphs can reason about some of the most important algorithms in computer science, including shortest-path and network flow.

Active learning is especially effective here because students can physically construct and traverse these structures, making abstract pointer relationships concrete before they encounter them in code.

Key Questions

1. Explain the fundamental differences between linear and non-linear data structures.
2. Compare different types of trees (e.g., binary trees) and their applications.
3. Analyze how graphs can model relationships in complex systems.

Learning Objectives

• Compare the hierarchical structure of a tree data structure with the network structure of a graph data structure.
• Classify different types of trees, such as binary trees, and explain their specific applications in computer science.
• Analyze how graph data structures can model real-world relationships in complex systems like social networks or transportation systems.
• Design a simple tree or graph to represent a given set of data or relationships.
• Explain the fundamental differences between linear and non-linear data structures, providing examples of each.

Before You Start

Introduction to Data Structures

Why: Students need a foundational understanding of basic data structures like arrays and linked lists to appreciate the non-linear nature of trees and graphs.

Basic Programming Concepts (Variables, Data Types, Control Flow)

Why: Understanding how data is stored and manipulated is crucial before abstracting to complex structures like trees and graphs.

Key Vocabulary

Node	A fundamental unit in a tree or graph, representing an entity or data point. Nodes are connected by edges.
Edge	A connection between two nodes in a graph or tree, representing a relationship or path. Edges can be directed or undirected.
Binary Tree	A specific type of tree data structure where each node has at most two children, referred to as the left child and the right child. This structure is efficient for searching and sorting.
Graph	A non-linear data structure consisting of nodes (vertices) and edges, where nodes can be connected to any other node. Graphs are used to model complex relationships.
Root Node	The topmost node in a tree data structure, from which all other nodes descend. It has no parent.

Watch Out for These Misconceptions

Common Misconception

Trees and graphs are just complicated lists.

What to Teach Instead

Linear structures assume a single path through data; trees and graphs model branching and network relationships that linear structures cannot represent accurately. When students physically build a tree or walk a graph, it becomes clear that the structure itself encodes meaning about the relationships between data points.

Common Misconception

All trees are binary trees.

What to Teach Instead

Binary trees are one specific type where each node has at most two children. Trees can have any branching factor -- a file system folder can contain hundreds of children. Exposure to multiple tree types through gallery walks prevents students from over-generalizing from the most common introductory example.

Active Learning Ideas

Collaborative Modeling: Build a Tree

Give each small group index cards and string. Students receive a set of data values and must construct a binary search tree by placing values in the correct nodes according to insertion rules. Groups then perform an in-order traversal by reading cards aloud in sequence, verifying the result is sorted.

35 min·Small Groups

Gallery Walk: Tree Type Museum

Set up stations around the room, each featuring a different tree type (binary tree, binary search tree, heap, trie, decision tree) with a diagram and two real-world applications. Students rotate through stations and record on a graphic organizer what access rule or property makes each type distinct.

40 min·Small Groups

Simulation Game: Graph Traversal Race

Students act as nodes in a graph drawn on the floor with tape. Each student-node holds a card with their neighbors' names. Two groups run breadth-first and depth-first traversal simultaneously, marking visited nodes with colored stickers. The class discusses which traversal found a target node faster and why.

30 min·Whole Class

Think-Pair-Share: Linear vs. Non-Linear Trade-offs

Students are given three data storage problems (contact list, org chart, city road map) and must individually decide whether a linear or non-linear structure fits best. They compare reasoning with a partner, then the class builds a shared decision framework on the whiteboard.

20 min·Pairs

Real-World Connections

• Social media platforms like Facebook and Twitter use graph data structures to represent user connections, friendships, and follower relationships, enabling features like friend suggestions and news feed algorithms.
• File systems on computers organize data hierarchically using tree structures, allowing for efficient navigation and management of directories and files, similar to how a company's organizational chart is structured.
• Mapping applications such as Google Maps or Waze utilize graph algorithms to find the shortest or fastest routes between locations, treating intersections as nodes and roads as edges.

Assessment Ideas

Exit Ticket

Provide students with a scenario, such as organizing a family tree or planning a road trip. Ask them to draw a representation of this scenario using either a tree or a graph, labeling at least four nodes and two edges. They should also write one sentence explaining why they chose that data structure.

Quick Check

Present students with two diagrams: one clearly representing a tree and another clearly representing a graph that is not a tree. Ask students to identify which is which and explain one key difference in their structure, focusing on parent-child relationships versus general connectivity.

Discussion Prompt

Facilitate a class discussion by asking: 'Imagine you are designing a system to recommend music based on listening habits. Would you use a tree or a graph? Explain your reasoning, considering how users and songs relate to each other.'

Frequently Asked Questions

What is the difference between a tree and a graph in data structures?

A tree is a restricted type of graph with no cycles and a single root node, where every non-root node has exactly one parent. A graph has no such constraints -- nodes can connect to any other nodes, creating cycles, and there is no required hierarchy. All trees are graphs, but not all graphs are trees.

Where are trees used in real software applications?

Trees are used in file systems (folders containing folders), HTML and XML document parsing (the DOM is a tree), database indexing (B-trees power most database indexes), decision-making systems, and compiler design for parsing code syntax. Binary search trees underpin many efficient search implementations.

How are graphs used to model real-world problems?

Graphs model any system with pairwise relationships: social networks (friendships), transportation networks (roads, flights), the internet (routers and connections), dependency management in software, and recommendation systems. Graph algorithms like Dijkstra's shortest path are used daily by navigation apps.

How does active learning support understanding trees and graphs?

Non-linear structures are difficult to visualize from a diagram alone. When students physically construct trees or act as nodes in a traversal simulation, the structural properties become tangible. Peer discussion during these activities also surfaces misunderstandings about direction, cycles, and node relationships that are hard to catch in individual practice.