Welcome to Tree Traversals!
In this chapter, we are going to explore how computers "walk" through a tree data structure. Imagine a family tree or a file system on your computer; these are all trees! To do anything useful with them—like searching for a file or printing a list of names—the computer needs a systematic way to visit every single node without getting lost.
Don't worry if this seems a bit abstract at first. Once you learn the "hidden path" tricks, you'll be able to trace these algorithms in your sleep!
Prerequisite Check: What is a Tree?
Before we walk, we need to know where we are standing. In Computer Science, a Tree is a collection of nodes connected by edges.
• The Root is the top node (the "boss").
• Nodes are the circles containing data.
• Children are nodes that branch out from a parent node.
• A Binary Tree is special: each node can have a maximum of two children (usually called Left and Right).
The Three Traversal Methods
A "traversal" is just a fancy word for visiting every node in a tree. For the AQA syllabus, you need to know three specific ways to do this. The names tell you exactly when you visit the Root node of any sub-section of the tree.
1. Pre-Order Traversal
In a Pre-order traversal, you visit the root BEFORE its children.
The order is: Root → Left → Right.
Memory Aid: "Pre" means "Before." The Root comes before the branches.
Step-by-Step Process:
1. Visit the Root node.
2. Traverse the left sub-tree.
3. Traverse the right sub-tree.
Real-World Use: Copying a Tree
If you want to clone a tree, you use Pre-order. You need to create the parent node before you can start attaching children to it!
2. In-Order Traversal
In an In-order traversal, the root is visited IN BETWEEN the left and right children.
The order is: Left → Root → Right.
Memory Aid: "In-order" results in "In-creasing" order for Binary Search Trees!
Step-by-Step Process:
1. Traverse the left sub-tree.
2. Visit the Root node.
3. Traverse the right sub-tree.
Real-World Use: Sorting
If you have a Binary Search Tree (BST), performing an In-order traversal will output the data in ascending order (e.g., 1, 2, 3... or A, B, C...).
3. Post-Order Traversal
In a Post-order traversal, you visit the root AFTER its children.
The order is: Left → Right → Root.
Memory Aid: "Post" means "After." The Root is the very last thing you visit.
Step-by-Step Process:
1. Traverse the left sub-tree.
2. Traverse the right sub-tree.
3. Visit the Root node.
Real-World Use: Deleting Trees and Math
• Emptying a tree: You must delete the children before you delete the parent (otherwise the children become "orphans" in memory!).
• Reverse Polish Notation (RPN): Post-order is used to convert standard math equations into a format computers can easily calculate using a stack.
The "Outline" Trick: How to Trace Any Tree
If you see a tree in an exam, don't panic! Use the Outline Method to find the answer in seconds. Imagine drawing a continuous line that hugs the outside of the tree, starting at the left of the root and following the shape all the way around.
To get the sequence:
• Pre-order: Write down the node's value when you pass the LEFT side of it.
• In-order: Write down the node's value when you pass the BOTTOM of it.
• Post-order: Write down the node's value when you pass the RIGHT side of it.
Quick Review: Left = Pre, Bottom = In, Right = Post.
Summary of Uses (Syllabus Requirements)
Did you know? Different traversals aren't just for fun; they have very specific jobs in software engineering. Here is exactly what you need to remember for your exam:
Pre-Order: Used for copying a tree structure.
In-Order: Used for outputting contents of a BST in ascending order.
Post-Order: Used for Infix to RPN conversions, producing a postfix expression, and emptying/deleting a tree.
Common Mistakes to Avoid
• Mixing up Left and Right: In all three traversals, Left always comes before Right. The only thing that changes position is the Root.
• Starting at the wrong place: Always start your trace at the Root (the very top), even if the algorithm tells you to go to the Left child first.
• Skipping leaf nodes: Every node must be visited, even the ones at the very bottom with no children!
Quick Key Takeaway Box
Pre-Order: Root-Left-Right (Copying)
In-Order: Left-Root-Right (Sorting/BST)
Post-Order: Left-Right-Root (RPN/Deleting)
Big-O Complexity: The time complexity for all three traversals is \(O(n)\) because you must visit every node exactly once.