1.
Binary Trees: What & Why
What is a Binary Tree?
A Binary Tree is a structure made up of nodes. Each node has:
• One data item
• One left pointer (to another node)
• One right pointer (to another node)
The first node is the root. Each node can have up to two children only.
Why Binary Trees?
• Binary trees are dynamic → size can grow/shrink as needed.
• They support fast search, insert, and delete operations (average O(log n)).
• Useful in sorting, searching, and hierarchical data (like filesystems).
2. Binary Tree Structure (Visual Examples)
Example Tree: Building from [50, 60, 30, 43, 19]
Successor Example: Delete 50 (root)
• In-order traversal: 19, 30, 43, 50, 60
• Successor of 50 is 60 → Replace 50 with 60
3. Traversals (Step-by-Step Algorithms)
What is Traversal?
Traversal = visiting each node once in a specific order.
Clock Concept
Use a clock to guide your thinking:
• 12 o’clock: visit
• 9 o’clock: go left
• 3 o’clock: go right
3.1 Pre-Order Traversal (N-L-R)
Algorithm:
1. Visit the root
2. Traverse the left subtree
3. Traverse the right subtree
Pseudocode:
Example Result: 50 30 19 43 60
3.2 In-Order Traversal (L-N-R)
Algorithm:
1. Traverse the left subtree
2. Visit the root
3. Traverse the right subtree
Pseudocode:
Example Result: 19 30 43 50 60 (in sorted order!)
3.3 Post-Order Traversal (L-R-N)
Algorithm:
1. Traverse left subtree
2. Traverse right subtree
3. Visit root
Pseudocode:
Example Result: 19 43 30 60 50
4. Constructing a Binary Tree (Pseudocode)
Insert Algorithm:
Insert(root, value):
IF root is NULL THEN
RETURN new Node(value)
IF value < root.data THEN
root.left = Insert(root.left, value)
ELSE
root.right = Insert(root.right, value)
RETURN root
Steps:
• Start from root
• If value < current node → go left
• Else → go right
• Repeat until empty spot is found
5. Deleting a Node (3 Cases)
Case 1: Node is a Leaf
• Just remove it
Case 2: Node has One Child
• Replace it with its child
Case 3: Node has Two Children
• Find in-order successor (leftmost of right subtree)
• Copy its value
• Delete the successor
Pseudocode:
Delete(root, value):
IF root is NULL THEN RETURN NULL
IF value < root.data THEN
root.left = Delete(root.left, value)
ELSE IF value > root.data THEN
root.right = Delete(root.right, value)
ELSE
IF root.left is NULL THEN RETURN root.right
IF root.right is NULL THEN RETURN root.left
successor = FindMin(root.right)
root.data = successor.data
root.right = Delete(root.right, successor.data)
RETURN root
FindMin(node):
WHILE node.left IS NOT NULL
node = node.left
RETURN node
6. Binary Tree Search (Pseudocode)
Pseudocode:
Search(root, item):
WHILE root IS NOT NULL
IF item = root.data THEN
RETURN FOUND
ELSE IF item < root.data THEN
root = root.left
ELSE
root = root.right
RETURN NOT FOUND
7. Summary Notes (Short Module Notes)
• Binary Tree = 2-child dynamic data structure
• Traversal Types:
o Pre-Order: Root → Left → Right
o In-Order: Left → Root → Right (sorted)
o Post-Order: Left → Right → Root
• Insertion = go left/right based on value
• Deletion = 3 cases (leaf, one child, two children)
• Search = same as BST insert, return if match
8. Practice Tasks
1. Draw the binary tree for: [70, 50, 90, 30, 60, 80, 100, 20]
2. Write in-order, pre-order, and post-order traversals.
3. Delete node 50. What’s the new tree?
4. Search for item 80: trace steps.
9. Exam-Style Multiple Choice Questions (MCQs)
1. What is the output of in-order traversal of this tree?
A. 40 20 10 30 60 80
B. 10 20 30 40 60 80
C. 10 30 20 40 80 60
D. 20 10 30 60 80 40
2. Which traversal method visits the root first, then left, then right? A. In-Order
B. Post-Order
C. Pre-Order
D. Reverse-Order
3. Which case is the most complex when deleting from a BST? A. Node with no children
B. Node with one child
C. Node with two children
D. Deleting the root
4. In a BST, where is the smallest element located? A. Rightmost node
B. Leftmost node
C. Root
D. It varies
10. Revision Sheet (Quick Review)
• Binary Tree: Max 2 children per node
• Insertion: Go left if smaller, right if larger
• Traversals:
o Pre-Order = Root → Left → Right
o In-Order = Left → Root → Right
o Post-Order = Left → Right → Root
• Deletion Cases:
o Leaf → remove directly
o One child → replace with child
o Two children → find successor
• Search: Repeat until match or NULL
• In-Order = Sorted order
• Dynamic structure = flexible size
End of Booklet. Designed for dummies. Focused on Zim A-Level needs.
Contact info :
email : tinodaishemchibi@gmail.com
phone (whatsapp) : +263 71 817 6525
Website: bluewave-portfolio-nexus
