# Binary Search Tree: Comprehensive C++ Implementation ## Introduction Binary Search Trees (BSTs) provide O(log n) average-case search/insert/delete operations through hierarchical ordering. This implementation covers all fundamental BST operations. ## Core Structure ```cpp\nstruct TreeNode { int value; TreeNode* left; TreeNode* right; TreeNode(int val) : value(val), left(nullptr), right(nullptr) {} }; TreeNode* root = nullptr;\n``` ### Key Operations 1. **Insertion**: Maintain BST property ```cpp\nTreeNode* insert(TreeNode* node, int val) { if (!node) return new TreeNode(val); if (val < node->value) node->left = insert(node->left, val); else if (val > node->value) node->right = insert(node->right, val); return node; // Return updated node }\n``` 2. **Deletion**: Three cases handling ```cpp\nTreeNode* deleteNode(TreeNode* node, int key) { if (!node) return nullptr; if (key < node->value) { node->left = deleteNode(node->left, key); } else if (key > node->value) { node->right = deleteNode(node->right, key); } else { // Case 1: No child if (!node->left && !node->right) { delete node; return nullptr; } // Case 2: One child if (!node->left) return node->right; if (!node->right) return node->left; // Case 3: Two children TreeNode* successor = minValueNode(node->right); node->value = successor->value; node->right = deleteNode(node->right, successor->value); } return node; }\n``` 3. **Traversals**: ```cpp\n// In-order (Sorted order) void inorder(TreeNode* node) { if (!node) return; inorder(node->left); cout << node->value << " "; inorder(node->right); } // Level-order (BFS) void levelOrder(TreeNode* root) { queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* current = q.front(); q.pop(); cout << current->value << " "; if (current->left) q.push(current->left); if (current->right) q.push(current->right); } }\n``` ### Complexity Analysis | Operation | Average | Worst | |-----------|---------|-------| | Search | O(log n) | O(n) | | Insert | O(log n) | O(n) | | Delete | O(log n) | O(n) | | Traversal | O(n) | O(n) | ## Applications - Database indexing - Auto-complete systems - File system hierarchies - Network routing tables - Game decision trees ### Best Practices 1. Use recursive algorithms 2. Always handle leaf node cases 3. Balance trees for performance 4. Implement destructors for memory cleanup 5. Validate BST properties during operations