Understanding Binary Search Trees (BSTs)
What Is a Binary Search Tree?
A Binary Search Tree (BST) is a type of binary tree where each node has at most two children, and the tree is organized based on the following properties:
- Left Child Property: All nodes in the left subtree of a node have values less than the node's value.
- Right Child Property: All nodes in the right subtree of a node have values greater than the node's value.
- Always restate the ordering rule (left < node < right) in answers.
- IB mark schemes expect this explicitly.
These properties ensure that a BST is always sorted, making it efficient for operations like searching, insertion, and deletion.
Structure of a BST
Structure of a BST
- A binary tree where each node has at most two children:
- Left child contains values smaller than the parent.
- Right child contains values greater than the parent.
- Ensures that the tree remains ordered, making searching efficient.
- Can be represented as a tree diagram with nodes and branches.
- Leaf Nodes: Nodes that have no children (both left and right pointers are null), marking the end of a branch in the tree.
- When drawing or describing a BST, always label the root, internal nodes, and leaf nodes.
- Use the ordering rule (left < parent < right) in explanations: examiners often award marks for explicitly stating this.
The root node is the starting point for all operations in a BST, while leaf nodes represent the endpoints of the tree's branches.
Common Mistake- Confusing leaf nodes with nodes that have one child: leaf nodes must have no children at all.
- Forgetting that BSTs are ordered: placing nodes randomly breaks the BST property.
Properties of a BST
- Ordered Structure: The left subtree of a node contains values less than the node, and the right subtree contains values greater than the node.
- Dynamic Size: BSTs can grow and shrink as nodes are inserted or deleted.
- Balanced vs. Unbalanced Trees:
- A balanced BST has a minimized depth, ensuring optimal search times.
- An unbalanced BST can degrade to a linked list, resulting in inefficient operations.
A balanced BST maintains a time complexity of $O(\log n)$ for search operations, while an unbalanced BST can degrade to $O(n)$.
Operations on a BST
Insertion
- Start at the Root: Begin at the root node.
- Compare Values:
- If the new value is less than the current node, move to the left child.
- If the new value is greater, move to the right child.
- Find the Correct Position: Repeat the comparison until an empty spot is found.
- Insert the Node: Place the new node in the correct position.
When inserting a node, always maintain the BST's ordering properties by comparing the new value with existing nodes.
Deletion
- Find the Node: Locate the node to be deleted.
- Three Cases:
- No Children: Simply remove the node.
