Binary Search Tree
Discrete Mathematical Structures [MAT 2101]
1. Binary Search Tree Anatomy & Terminology
A Binary Search Tree is a structured way to store data to perform operations like insertion, deletion, and lookup efficiently.
A binary search tree consists of key components:
- Node: A basic element of a tree that stores a value or data.
- Root Node: The topmost node of a tree, which has no parent.
- Parent Node: A node that has one or more child nodes.
- Child Node: A node directly connected below another node.
- Leaf Node: A node that has no children.
- Edge: A connection between two nodes.
- Subtree: A smaller tree formed by a node and all its descendants.
- Ancestor: Any node that lies above another node along the path towards the root.
- Descendant: A node that lies below another node within its subtree.
2. Tree vs. Binary Tree
A node can have any number of child nodes.
Each node has at most two children (Left & Right).
3. Insertion Operation
- If the tree is empty, the current value becomes the root.
- Compare the values:
- If the value is smaller than the node at that point, move towards the left.
- If the value is larger than the node at that point, move towards the right.
4. Deletion Cases
Case 1: Delete Leaf Node
Example: Delete "50"
Rule: Simply remove the leaf node directly.
Case 2: Node with 1 Child
Example: Delete "60"
Rule: Delete node and connect child directly to ancestor.
Case 3: Node with 2 Children
Example: Delete "40"
Rule: Replace node with its in-order successor.
5. Tree Traversals
Pre-Order
Root → Left → Right
Record when visiting node for the 1st time.
56 → 30 → 20 → 40 → 70 → 60 → 80
In-Order
Left → Root → Right
Record when visiting node for the 2nd time.
20 → 30 → 40 → 56 → 60 → 70 → 80
Post-Order
Left → Right → Root
Record when visiting node for the last time.
20 → 40 → 30 → 60 → 80 → 70 → 56
6. Practice Questions & Case Studies
Delete the node with value "30" from the given tree structure:
Draw the tree whose in-order traversal is: f, a, g, b, h, d, i, c, j, e and post-order traversal is: f, g, a, h, i, d, j, e, c, b.
Find the in-order, pre-order, and post-order traversal of the tree given:
A company wants to organize its employee data using a binary search tree (BST). Each employee is identified by a unique employee ID, and the IDs are stored in a BST for efficient searching and retrieval. Currently, the tree contains employee IDs.
a) The company hires a new employee with ID 65. Insert this ID into the BST and provide the updated structure of the tree.
b) The company removes an employee with ID 70. Update the tree using the in-order successor method and show the new structure.
A computer system stores the following values in a Binary Search Tree: 35, 20, 50, 10, 25, 40, 60, 5, 15, 30.
a) Construct the BST by inserting the values in the given order.
b) Determine the height of the tree and the number of comparisons required to search for the element 30.
c) Explain the best-case and worst-case time complexities of searching in a BST. How does the height of the tree influence searching efficiency?
A cybersecurity system maintains a Binary Search Tree to store unique numerical identifiers associated with suspicious network activities. The identifiers received sequentially are: 45, 25, 65, 15, 35, 55, 75, 30, 40.
a) Construct the corresponding BST.
b) A new suspicious identifier, 33, is detected. Insert it into the existing BST and show the updated tree.
c) The identifier 25 must be removed. Perform the deletion using the in-order successor method and explain the changes.
d) Discuss one advantage and one limitation of using a BST for managing dynamically changing security records.
A computer system stores student registration numbers using a Binary Search Tree. Consider the following two sequences:
- Sequence A: 10, 20, 30, 40, 50, 60, 70
- Sequence B: 40, 20, 60, 10, 30, 50, 70
a) Construct two BSTs by inserting the elements in the given order.
b) Determine the height of each tree.
c) Find the number of comparisons required to search for the element 70 in each tree.
d) Based on your results, explain how the insertion order affects the structure and searching efficiency of a BST.