Computer Science · 12th Grade · Object-Oriented Design and Data Structures · Weeks 10-18

Binary Trees and Tree Traversals

Students are introduced to binary trees and implement various traversal methods (in-order, pre-order, post-order).

• Common Core State Standards
• CSTA: 3B-AP-12
• CSTA: 3B-AP-14

About This Topic

Binary trees are the gateway to a broad family of hierarchical data structures that solve problems linear structures like arrays and linked lists cannot handle efficiently. In 12th-grade computer science, students build binary tree implementations from scratch, defining TreeNode classes with left and right child references, and implement the three classic recursive traversal algorithms: in-order, pre-order, and post-order. This topic connects directly to CSTA standard 3B-AP-14, developing the recursive thinking and pointer-based design skills that are central to advanced computer science.

The traversal algorithms are more than implementation exercises: each produces a different ordering of the tree's values with specific applications. In-order traversal of a binary search tree produces sorted output. Pre-order traversal is used for creating copies or prefix expression evaluation. Post-order traversal appears in memory deallocation and postfix expression evaluation. Understanding why each traversal visits nodes in its particular order requires students to trace the algorithm recursively, building a precise mental model of how recursive calls unwind through a tree structure.

Active learning is highly effective here because tree traversal is one of the topics where students most benefit from visualizing the recursion stack. Physical or drawn call trees, group tracing exercises, and collaborative debugging of traversal code all help students move from confusion to confidence faster than individual study alone.

Key Questions

1. In what ways do tree structures mirror real-world organizational hierarchies?
2. Differentiate between the applications of various tree traversal methods.
3. Construct a binary tree and demonstrate its traversal using different algorithms.

Learning Objectives

• Design and implement a binary tree data structure in a programming language, including node creation and child linking.
• Analyze the recursive nature of in-order, pre-order, and post-order traversals by tracing their execution on sample trees.
• Compare and contrast the output sequences generated by in-order, pre-order, and post-order traversals for a given binary tree.
• Evaluate the efficiency and applicability of each traversal method for specific computational tasks, such as sorting or expression evaluation.
• Create a program that demonstrates the functionality of a binary tree and its three primary traversal algorithms.

Before You Start

Recursion

Why: Students must understand how functions can call themselves to grasp the recursive nature of tree traversals.

Pointers and References

Why: Implementing tree nodes requires understanding how variables can refer to other objects in memory, specifically for linking parent and child nodes.

Basic Data Structures (Arrays, Linked Lists)

Why: Familiarity with linear data structures provides a foundation for understanding the advantages and differences of hierarchical structures like trees.

Key Vocabulary

Binary Tree	A tree data structure where each node has at most two children, referred to as the left child and the right child.
Node	An element within a tree structure that contains data and references (pointers) to its children.
Traversal	The process of visiting each node in a tree exactly once, in a systematic order.
In-order Traversal	A tree traversal method that visits the left subtree, then the current node, then the right subtree. For a binary search tree, this yields sorted data.
Pre-order Traversal	A tree traversal method that visits the current node first, then the left subtree, then the right subtree. Useful for copying trees or creating prefix expressions.
Post-order Traversal	A tree traversal method that visits the left subtree, then the right subtree, then the current node. Often used for deleting nodes or evaluating postfix expressions.

Watch Out for These Misconceptions

Common Misconception

All three tree traversals produce the same output.

What to Teach Instead

Each traversal visits nodes in a different order. In-order places the current node between its left and right subtrees; pre-order visits the current node first; post-order visits it last. The outputs are identical only for single-node trees. Drawing the same tree with all three traversals side by side makes the differences unmistakable.

Common Misconception

Tree traversals require iteration rather than recursion.

What to Teach Instead

Tree traversals have elegant recursive implementations because a tree is itself a recursive structure: each subtree is also a binary tree. While iterative traversals using explicit stacks exist, the recursive implementations are more directly readable and build crucial recursive thinking skills. Students who use iteration exclusively miss the conceptual link between tree structure and recursion.

Common Misconception

Post-order traversal is just in-order traversal done backwards.

What to Teach Instead

Post-order visits the left subtree, right subtree, then the root. This is not simply the reverse of in-order, which visits left, root, right. Reversed in-order would visit right, root, left, which is a different sequence entirely. Tracing both post-order and reversed in-order on the same tree to compare outputs clarifies this distinction.

Active Learning Ideas

Simulation Game: Walk the Tree

Arrange 7-10 students as a binary tree, each holding a number card. A designated traversal walker follows the rules for in-order, pre-order, or post-order traversal, physically moving between students and reading numbers aloud. After each traversal, the class records the output and compares orderings. The walker then switches rules and the class predicts the output before it happens.

30 min·Whole Class

Collaborative Diagramming: Trace the Recursion

Pairs receive a printed binary tree diagram and hand-trace an in-order traversal, drawing the recursive call stack step by step below the tree. They annotate which node is currently being visited, which calls are pending, and when a base case (null node) is reached. After completing in-order, they trace pre-order and compare the call stack drawings to identify exactly where the visit step differs.

40 min·Pairs

Gallery Walk: Traversal Applications

Set up 4 stations, each showing a real application of a tree traversal: expression tree evaluation, directory structure listing, compiler abstract syntax tree, and XML/HTML parsing. Student pairs read the scenario, identify which traversal type is most appropriate, and write a 3-sentence justification. Groups compare answers during debrief, focusing on cases where multiple traversals could work.

35 min·Pairs

Collaborative Lab: Build and Traverse

Small groups collaboratively implement a BinaryTree class with insert and three traversal methods, with each group member responsible for one traversal. They combine their implementations, run all three traversals on the same tree, verify outputs match expected orderings, and then write a test case that would fail if two traversal methods were accidentally swapped.

55 min·Small Groups

Real-World Connections

• File systems on computers organize directories and files in a hierarchical tree structure. Navigating these file systems often implicitly uses tree traversal algorithms to locate or list files.
• Compilers use abstract syntax trees (ASTs) to represent the structure of source code. Traversing these trees, particularly pre-order and post-order, is crucial for tasks like code analysis, optimization, and generating machine code.
• Decision trees are used in machine learning and data analysis to model decisions and their possible consequences. Algorithms traverse these trees to classify data or make predictions.

Assessment Ideas

Quick Check

Provide students with a small, pre-drawn binary tree. Ask them to write down the sequence of nodes visited for each of the three traversal types (in-order, pre-order, post-order) on a whiteboard or shared document. Review responses to identify common misconceptions.

Exit Ticket

Present students with a binary search tree and a specific value. Ask them to write the output of an in-order traversal. Then, ask them to explain in one sentence why this traversal produces sorted output.

Discussion Prompt

Pose the question: 'When might you want to delete all the nodes in a binary tree, and which traversal method would be most efficient or safest to use for that purpose?' Facilitate a class discussion comparing post-order traversal's suitability for deallocation.

Frequently Asked Questions

What is the difference between in-order, pre-order, and post-order traversal?

All three traversals visit every node exactly once but in different sequences. In-order visits the left subtree, then the current node, then the right subtree. Pre-order visits the current node first, then left, then right. Post-order visits left, right, then the current node last. The 'order' refers to when the current node is visited relative to its children.

How does active learning help students understand tree traversals?

Physically acting out traversals in the classroom, where students represent nodes and a designated walker follows the traversal rules, makes the recursive visiting sequence visible and memorable. When students can predict the output of a traversal they just physically walked through, they have internalized the algorithm in a way that code reading alone rarely achieves.

Where are binary trees used in real software?

Binary trees appear in file systems (directory hierarchies), compiler design (abstract syntax trees), HTML rendering (the DOM is a tree), game AI (decision trees), and database indexing. The traversal algorithms map directly to operations in each context, such as rendering child elements before parent layout in a post-order DOM traversal.

How do you implement tree traversal without recursion?

An iterative traversal uses an explicit stack to simulate the call stack that recursion manages automatically. For in-order traversal, you push nodes as you descend left, then process a node and explore its right subtree when you backtrack. This approach is useful in environments with limited stack space or when explicit control of the traversal order is needed.