Trees and binary search trees

Introduction to Trees

Welcome to the world of hierarchical data! Up until now, you might have studied "linear" data structures like Stacks and Queues or Linked Lists, where data follows a straight line. However, a lot of information in the real world isn't linear—it’s organized in layers or hierarchies.

Think about your computer's folder system: a "Documents" folder contains sub-folders, and those sub-folders contain files. Or think about a family tree showing ancestors and descendants. In Computer Science, we use Trees to represent these types of relationships. As an HL student, mastering trees is a major step toward understanding how complex data is efficiently stored and searched.

What is a Tree?

A Tree is a non-linear data structure made up of nodes connected by edges. It is a collection of elements where each element can have multiple "children" but only one "parent."

Key Terminology

Don't worry if there are many terms; they mostly use family-based analogies!

1. Node: An individual element in the tree that contains data.
2. Root: The very top node of the tree. It is the only node that has no parent. Every tree has exactly one root.
3. Parent: A node that has edges leading down to other nodes.
4. Child: A node that is connected to a node above it (its parent).
5. Leaf: A node that does not have any children. These are the "end points" of the tree.
6. Subtree: Any node and all its descendants can be viewed as a smaller tree within the larger one.
7. Height: The number of edges on the longest path from the root to a leaf node.

Real-World Analogy: Think of a corporate organizational chart. The CEO is the Root. The Managers are Parents to their teams (the Children). The employees who don't manage anyone else are the Leaves.

Quick Review: Tree Rules

• A tree cannot have cycles (you can't follow a path and end up back where you started).
• Every child has exactly one parent.
• All nodes must be reachable from the root.

Binary Trees

In this course, we focus heavily on Binary Trees. A binary tree is a special type of tree where each node can have at most two children. We usually refer to them as the Left Child and the Right Child.

Did you know? Even though a node can have two children, it is perfectly fine for a node in a binary tree to have only one child, or zero children (a leaf).

Binary Search Trees (BST)

A Binary Search Tree (BST) is a binary tree that follows a specific ordering rule. This rule makes searching for data incredibly fast.

The BST Ordering Rule:

For every node in the tree:
1. All values in the left subtree must be less than the node's value.
2. All values in the right subtree must be greater than the node's value.

Example: If the root is \(50\), the left child could be \(30\) (because \(30 < 50\)) and the right child could be \(70\) (because \(70 > 50\)).

Why use a BST?

In a simple list of \(n\) items, finding a specific item might take \(n\) steps. In a balanced BST, finding an item usually takes only \(\log n\) steps. This is similar to the efficiency of a Binary Search algorithm you may have learned in B.1 Computational thinking.

Common Operations in a BST

1. Searching for a Value

To find a value \(V\) in a BST:
1. Start at the Root.
2. If the current node is null, the value isn't there.
3. If the current node equals \(V\), you found it!
4. If \(V\) is less than the current node, move to the Left Child.
5. If \(V\) is greater than the current node, move to the Right Child.
6. Repeat until found or you hit a leaf.

2. Inserting a Value

To insert a new value, we follow the same logic as searching. We "search" for where the value should be. Once we find an empty spot (a null child) that follows the ordering rule, we place the new node there.

Common Mistake: Students often try to "re-arrange" the whole tree when adding a node. Don't! Just follow the left/right rules until you find an empty spot at the bottom of the tree.

Tree Traversals

Traversal means "visiting" every node in the tree exactly once. There are three standard ways to do this for binary trees. The names refer to when the Parent (Root) is visited relative to its children.

1. Pre-order Traversal

Order: Root \(\rightarrow\) Left \(\rightarrow\) Right
The node is visited first, then we go left, then right. This is often used to "copy" a tree structure.

2. In-order Traversal

Order: Left \(\rightarrow\) Root \(\rightarrow\) Right
This is the most popular traversal for BSTs. If you perform an In-order traversal on a Binary Search Tree, the values will be visited in ascending (sorted) order!

3. Post-order Traversal

Order: Left \(\rightarrow\) Right \(\rightarrow\) Root
The children are visited first, and the root is visited last. This is useful for deleting trees or evaluating mathematical expression trees.

Memory Trick: "The Parent is the Key"

• Pre-order: Parent is First.
• In-order: Parent is in the Middle.
• Post-order: Parent is Last.

Summary and Key Takeaways

• Trees are hierarchical structures consisting of nodes and edges.
• The Root is the top; Leaves are at the bottom.
• Binary Trees limit each node to a maximum of 2 children.
• Binary Search Trees (BST) follow the rule: \(Left < Parent < Right\).
• Searching in a BST is efficient with a complexity often approaching \(O(\log n)\).
• Traversals (In-order, Pre-order, Post-order) determine the sequence in which nodes are processed.

Note: For more information on how trees compare to other structures, see the chapter on Graphs and traversals or Linked lists.