Binary Tree & Binary Search Tree ā Complete Step-by-Step Guide
Module 9 & 10 ā Binary Tree & Binary Search Tree: Structure, Traversals, BST Search, Insertion & Deletion Structured as Topic ā Plain-English Explanation ā Real Code ā Visual Diagram ā Complexity ā Common Pitfalls.
1. Binary Tree Basics (Module 9)
A tree is a hierarchical structure made of nodes connected by edges, starting from a single root node with no parent. A binary tree restricts every node to at most two children, conventionally called the left child and the right child. Trees naturally represent hierarchical relationships ā file systems, organization charts, and the structure behind faster search operations.
struct Node {
int data;
Node* left;
Node* right;
};
2. Tree Traversals (Module 9)
Traversal means visiting every node exactly once, and the order in which you visit them defines four classic strategies:
void inorder(Node* n) {
if (!n) return;
inorder(n->left);
cout << n->data << " ";
inorder(n->right);
}
// For the tree above: 3 5 8 10 15
| Traversal | Order | Typical Use |
|---|---|---|
| Preorder | Root $\to$ Left $\to$ Right | Copying / serializing a tree |
| Inorder | Left $\to$ Root $\to$ Right | Sorted output from a BST |
| Postorder | Left $\to$ Right $\to$ Root | Deleting a tree safely |
| Level-order | Top row to bottom row | Shortest-path style problems, BFS on trees |
3. BST Structure & Search (Module 10)
A Binary Search Tree (BST) is a binary tree with one crucial ordering rule: for every node, every value in its left subtree is smaller than the node's value, and every value in its right subtree is larger. This rule is what makes searching fast ā at each node you can immediately decide to go left or right, discarding half the remaining tree, much like binary search on an array.
Node* search(Node* root, int target) {
if (!root || root->data == target) return root;
if (target < root->data) return search(root->left, target);
return search(root->right, target);
}
- Complexity: $O(\log n)$ for search/insert/delete on a balanced BST, but $O(n)$ in the worst case if the tree becomes a skewed chain.
4. Insertion & Deletion (Module 10)
Insertion follows the same left/right comparison logic as search, walking down until it finds an empty spot that respects the BST rule, then attaches the new node there.
Deletion is trickier:
- Deleting a leaf: Trivial ā simply remove it and set parent pointer to null.
- Deleting a node with one child: Reconnects its parent directly to that child.
- Deleting a node with two children: Requires finding its in-order successor (the smallest value in its right subtree) to replace it, keeping the BST property intact.
