CO2412 Computational Thinking Lecture 9 Notes

CO2412: Computational Thinking
Lecture 9

Introduction to Binary Search Trees (BST)
1. Binary Tree Structure
o A Binary Tree is a hierarchical structure where each node has a
maximum of two children: a left child and a right child.
o Key Components:

 Root Node: The topmost node in the tree.
 Leaf Nodes: Nodes without children.
 Edges: Connections between nodes.
Binary Search Trees (BST)
1. Definition and Properties
o A Binary Search Tree is a type of binary tree where each node
follows a specific order:
 The left child’s value is less than its parent node’s value.
 The right child’s value is greater than its parent node’s value.
o This property allows for efficient searching, insertion, and deletion
operations.
2. Searching in a BST
o To find a value, start at the root and compare the value with the
node’s value:
 If the value is less, move to the left child.
 If the value is greater, move to the right child.
 Repeat this process until the value is found or the subtree is
exhausted.
Example:
To find the value 8:
 Start at the root (9), move left (6), then move right (8) to find
the value.