Chapter: Trees
Welcome! In this chapter, we are going to explore Trees. In Computer Science, a tree isn't something with leaves and bark that grows in a park. Instead, it is a way of organizing data so that we can find, add, and delete information very quickly. If you have ever used the "File Explorer" on your computer to look through folders, you have already used a tree structure!
Don't worry if this seems a bit abstract at first. We will break it down step-by-step with simple analogies to make sure you feel confident.
1. What is a Tree?
In technical terms, a tree is a non-linear data structure. Unlike an array or a list (which are like a single line of people), a tree branches out in different directions.
Key Terminology
To understand trees, we need to learn the "family" language used to describe them:
- Node: This is an individual data item in the tree (like a single person in a family tree).
- Edge: The link or line that connects two nodes.
- Root: The very top node in a tree. Every tree has exactly one root.
- Parent: A node that has edges leading down to other nodes.
- Child: A node that has an edge leading to it from a node above it.
- Leaf: A node that has no children (it is at the very end of a branch).
- Subtree: A smaller section of a tree that is a tree itself.
Real-World Analogy: Think of a Company Hierarchy. The CEO is the Root. The Managers are Parents to the employees, and the employees are the Children. The employees at the very bottom who don't manage anyone else are the Leaves.
Quick Review:
• The Root is the only node with no parent.
• Leaves are the only nodes with no children.
• An Edge connects a parent to a child.
2. Binary Trees
A Binary Tree is a specific type of tree that follows one simple rule: Each node can have a maximum of two children.
Imagine a person having at most two children. In a binary tree, we usually refer to these as the Left Child and the Right Child.
Did you know? Binary trees are incredibly efficient. If you have a perfectly balanced binary tree with 1,000 items, you can find any specific item in only about 10 steps!
Binary Search Trees (BST)
A Binary Search Tree is a binary tree where the data is kept in a specific order to make searching even faster. The rule is:
- Values smaller than the parent go to the Left.
- Values larger than the parent go to the Right.
Example: If the Root is 10, and you want to add 5, it goes to the left. If you want to add 15, it goes to the right.
Key Takeaway:
The golden rule for BSTs is: Left is Less, Right is More.
3. Tree Traversals
Traversal is just a fancy word for "visiting every node in the tree once." Depending on the order in which we visit the nodes, we get different results. There are three main types you need to know:
1. Pre-order Traversal
In this version, we visit the Root first, then the Left subtree, then the Right subtree.
Mnemonic: Root is Pre (Before) everything else.
2. In-order Traversal
We visit the Left subtree, then the Root, then the Right subtree.
Mnemonic: The Root is In the middle.
Pro-tip: If you do an In-order traversal on a Binary Search Tree, the numbers will come out in perfect numerical order!
3. Post-order Traversal
We visit the Left subtree, then the Right subtree, and finally the Root.
Mnemonic: Root is Post (After) everything else.
How to do it easily (The "Outline" Trick):
If you have a diagram of a tree, draw a single continuous line starting at the left of the root and trace all the way around the outside of the tree (like you are wrapping it in string).
• Pre-order: Mark the node as you pass the left side of it.
• In-order: Mark the node as you pass the bottom of it.
• Post-order: Mark the node as you pass the right side of it.
4. Adding and Searching in a BST
Searching for a value in a Binary Search Tree is like playing a game of "Higher or Lower."
Step-by-Step Search:
- Start at the Root.
- Is the value you are looking for equal to the current node? If yes, you found it!
- Is the value smaller? Move to the Left Child and repeat step 2.
- Is the value larger? Move to the Right Child and repeat step 2.
- If you reach a point where there is no child to move to, the value is not in the tree.
Common Mistake:
Students often forget that when adding a node, you must follow the search rules until you find an empty spot (a leaf). You don't just put it anywhere! You must compare it to every parent node along the way.
Quick Review Box:
To Search or Add:
1. Start at Root.
2. Compare.
3. Smaller? Go Left.
4. Bigger? Go Right.
5. Repeat until found or empty space reached.
Summary Checklist
Check your understanding:
[ ] Can I define Root, Parent, Child, and Leaf?
[ ] Do I know that a Binary Tree has a max of 2 children per node?
[ ] Can I remember the "Left is Less" rule for Search Trees?
[ ] Can I perform In-order, Pre-order, and Post-order traversals?
Great job! Trees are a fundamental part of Computer Science. Once you master the "Left vs Right" logic, you've conquered the hardest part.