Computer Science
Grade 10
20 min
Binary Search Trees
Binary Search Trees
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define a Binary Search Tree (BST) and its core properties.
Differentiate between a node, root, parent, child, and leaf in a BST.
Trace the step-by-step process of inserting a new value into a BST.
Trace the algorithm for searching for a value within a BST.
By the end of of this lesson, students will be able to describe the three main tree traversal methods: In-Order, Pre-Order, and Post-Order.
Explain why a balanced BST is more efficient for searching than a simple list.
Implement a basic Node class using Object-Oriented Programming concepts.
Ever wonder how a dictionary or your phone's contact list can find a specific entry almost instantly, even with thousands of items? 📖🔍
A Binary Search Tree (BST) is a powerful data structure that organizes...
2
Key Concepts & Vocabulary
TermDefinitionExample
NodeThe fundamental building block of a tree. Each node contains a piece of data and references (or 'pointers') to at most two other nodes: a left child and a right child.In a tree of numbers, a node might hold the value `10`, a reference to a node with `5` as its left child, and a reference to a node with `15` as its right child.
RootThe very first node at the top of the tree. It is the only node that does not have a parent.If we insert the numbers `[10, 5, 15]`, the node with the value `10` would be the root of the tree.
Parent / Child / LeafA node is a 'parent' to the nodes directly connected below it (its 'children'). A 'leaf' is a node that has no children.In a tree with a root `10` and children `5` and `15`, `10` is the p...
3
Core Syntax & Patterns
The Binary Search Tree Property
For any node `N`:
1. All values in `N`'s left subtree are LESS THAN `N`'s value.
2. All values in `N`'s right subtree are GREATER THAN `N`'s value.
3. Both the left and right subtrees must also be binary search trees.
This is the most important rule. It must be maintained at all times when inserting or deleting nodes. This property is what makes searching so efficient.
Insertion Algorithm
1. Start at the root.
2. Compare the new value with the current node's value.
3. If the new value is smaller, move to the left child. If the new value is larger, move to the right child.
4. If the required child node is empty (null), insert the new node there.
5. If not, repeat from step 2 with the child node as the new current node....
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
Why does an In-Order traversal of any valid Binary Search Tree always produce the node values in sorted, ascending order?
A.It's a coincidence that only works for the example tree.
B.Because the traversal algorithm sorts the values as it finds them.
C.Because the traversal recursively visits the entire left (smaller) subtree before visiting the root, which is then followed by the entire right (larger) subtree.
D.Because the In-Order traversal visits the shallowest nodes first.
Challenging
The Pre-Order traversal of a BST is `[30, 15, 25, 45, 40]`. What is the Post-Order traversal of the same tree?
A.15, 25, 30, 40, 45
B.25, 15, 40, 45, 30
C.15, 40, 25, 45, 30
D.It is impossible to determine from the Pre-Order traversal alone.
Challenging
You are given the numbers `[20, 10, 30]`. Which other insertion order of these same three numbers would result in the exact same final BST structure?
A.[10, 30, 20]
B.[30, 10, 20]
C.[10, 20, 30]
D.No other order would produce the same tree.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing Free