Introduction to Binary Trees

Welcome to one of the most powerful ways to organize data! While stacks and queues are "linear" (like a line of people), a Binary Tree is a "hierarchical" data structure. Think of it like a family tree or the folder structure on your computer. In this chapter, we will learn how to build these structures and why they make finding information so much faster. Don't worry if it looks like a complex web at first—once you understand the simple "left-right" rule, everything else falls into place!

1. What is a Binary Tree?

A Binary Tree is a collection of nodes. Every tree starts with a single node at the very top called the Root. Each node in a binary tree can have a maximum of two children. We call these the Left Child and the Right Child.

Key Terminology

- Root: The top-most node of the tree. There is only one root. - Parent: A node that has other nodes branching from it. - Child: A node that descends from a parent node. - Leaf: A node that has no children (the "end" of a branch). - Subtree: A smaller tree within a larger tree (e.g., a node and all its descendants). Quick Analogy: Imagine a CEO (Root) who manages two Managers (Children). Each Manager might manage two Supervisors, and so on. If a worker has no one reporting to them, they are a Leaf!

Note: For more on how to visit every node in a tree, check out the chapter on "Tree Traversals".

2. The Binary Search Tree (BST)

A Binary Search Tree (BST) is a special type of binary tree that follows a specific rule to keep data organized. This rule makes searching incredibly efficient.

The BST Rule:

For every node in the tree: - All values in the left subtree must be smaller than the node's value. - All values in the right subtree must be larger than the node's value. Example: If the root is 50, the number 30 must go to the left, and 70 must go to the right.

3. Operations on Binary Search Trees

Searching for a Value

To find a value in a BST, you don't need to look at every node. You simply: 1. Start at the Root. 2. If the value you want is equal to the current node, you found it! 3. If the value is smaller, move to the Left Child. 4. If the value is larger, move to the Right Child. 5. Repeat until you find the value or hit an empty spot (meaning the value isn't there).

Inserting a Value

Inserting follows the exact same logic as searching. You "search" for the value until you find an empty spot (a None reference), and that is where the new node is placed. Important Syllabus Note: In the GCE A-Level 9569 curriculum, you are required to know how to search and insert for BSTs, but you are excluded from having to perform editing or deleting nodes from a Binary Search Tree. This makes your life much easier!

4. Implementing a Binary Tree in Python

To build a tree in Python, we use Object-Oriented Programming (OOP). We create a Node class where each object stores its data and a reference to its two children. The Node Structure:
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None

Python Logic for Insertion:

To insert into a BST, we can use a simple function:
def insert(root, value):
if root is None:
return Node(value)
if value < root.data:
root.left = insert(root.left, value)
else:
root.right = insert(root.right, value)
return root Did you know? This code uses Recursion (a function calling itself). It keeps moving down the tree until it finds the perfect empty spot for the new data.

5. Efficiency and Big-O Notation

In Computing, we measure how "fast" an algorithm is using Big-O notation.

Worst-Case Time Complexity

Imagine you insert numbers into a BST in perfect order: 10, 20, 30, 40, 50. The tree will just look like one long line (a skewed tree). In this worst-case scenario, if you are searching for 50, you have to look at every single node. Therefore, the worst-case time complexity for searching or inserting in a Binary Search Tree is:

\(O(n)\)

where \(n\) is the number of nodes in the tree. Common Mistake to Avoid: Many students assume BSTs are always fast. Remember, if the tree is not "balanced" and looks like a straight line, it performs just like a Linked List!

6. Summary and Key Takeaways

Key Takeaways:
- A Binary Tree is a structure where each node has at most two children. - A Binary Search Tree (BST) follows the rule: Left < Parent < Right. - Searching and Inserting are efficient because you can ignore half the tree at each step (if the tree is balanced). - Syllabus Tip: You only need to know how to create, search, and insert for BSTs. Deletion is not required for BSTs in this exam! - The worst-case time complexity is \(O(n)\).

Quick Review: If you have a root node of 25 and you want to insert 10, which side does it go on? If you said Left, you're ready for the next chapter!