A Binary Search Tree (BST) is a specialized binary tree structure where each node's left subtree contains only values less than the node's key, and its right subtree contains only values greater than the key. This property must hold recursive for all subtrees. An in-order traversal of a BST yields the keys in sorted order, which is why it's also called a Binary Sort Tree.

Its primary utility lies in efficient search operations. Unlike binary search on arrays, whicch requires contiguous memory and sorted data, a BST can perform lookups by comparing the target key with the root and eliminating one entire subtree from consideration. Search efficiency ranges from O(log N) in balanced trees (like complete or nearly complete BSTs) to O(N) in degenerate cases (like skewed trees).

Node Structure and Basic Class Definition

template<typename K>
struct BSTNode {
    K key;
    BSTNode* left;
    BSTNode* right;

    BSTNode(const K& k) : key(k), left(nullptr), right(nullptr) {}
};

template<typename K>
class BSTree {
    typedef BSTNode<K> Node;
    Node* root;

public:
    BSTree() : root(nullptr) {}
    ~BSTree() { clear(root); }

    // Core operations
    bool insert(const K& key);
    bool remove(const K& key);
    Node* find(const K& key) const;
    void inOrder() const;

private:
    void clear(Node*& node);
    void inOrder(Node* node) const;
};

Core Operations: Insertion and Search

Insertion locates the appropriate position while maintaining the BST property. Duplicate keys are typically not allowed.

template<typename K>
bool BSTree<K>::insert(const K& key) {
    if (!root) {
        root = new Node(key);
        return true;
    }

    Node* parent = nullptr;
    Node* current = root;

    while (current) {
        parent = current;
        if (key == current->key) {
            return false; // Duplicate
        } else if (key < current->key) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    current = new Node(key);
    if (key < parent->key) {
        parent->left = current;
    } else {
        parent->right = current;
    }
    return true;
}

Search leverages the BST property to navigate left or right based on comparisons.

template<typename K>
typename BSTree<K>::Node* BSTree<K>::find(const K& key) const {
    Node* current = root;
    while (current) {
        if (key == current->key) {
            return current;
        } else if (key < current->key) {
            current = current->left;
        } else {
            current = current->right;
        }
    }
    return nullptr;
}

Deletion Operation

Deletion is the most complex operation, with three main cases:

1. Leaf Node: Simply remove it.
2. Node with One Child: Replace the node with its only child.
3. Node with Two Children: Replace the node's key with the in-order predecessor (maximum in left subtree) or successor (minimum in right subtree), then delete that predecessor/successor node.

template<typename K>
bool BSTree<K>::remove(const K& key) {
    if (!root) return false;

    Node* parent = nullptr;
    Node* target = root;

    // Locate the node to delete and its parent
    while (target && target->key != key) {
        parent = target;
        if (key < target->key) {
            target = target->left;
        } else {
            target = target->right;
        }
    }
    if (!target) return false; // Key not found

    // Case 1 & 2: Node has at most one child
    if (!target->left || !target->right) {
        Node* child = target->left ? target->left : target->right;

        if (!parent) { // Deleting the root
            root = child;
        } else if (parent->left == target) {
            parent->left = child;
        } else {
            parent->right = child;
        }
        delete target;
    }
    // Case 3: Node has two children
    else {
        // Find in-order predecessor (max of left subtree)
        Node* predecessorParent = target;
        Node* predecessor = target->left;
        while (predecessor->right) {
            predecessorParent = predecessor;
            predecessor = predecessor->right;
        }

        // Replace target's key with predecessor's key
        target->key = predecessor->key;

        // Detach and delete the predecessor node
        // (Predecessor has at most a left child)
        if (predecessorParent->left == predecessor) {
            predecessorParent->left = predecessor->left;
        } else {
            predecessorParent->right = predecessor->left;
        }
        delete predecessor;
    }
    return true;
}

Recursive Implementations

Using references simplifies recursive implementations, especially for insertion and deletion, by allowing direct modification of parent pointers.

// Recursive Insert Helper
template<typename K>
bool insertRecursive(Node*& node, const K& key) {
    if (!node) {
        node = new Node(key);
        return true;
    }
    if (key == node->key) return false;
    if (key < node->key) return insertRecursive(node->left, key);
    else return insertRecursive(node->right, key);
}

// Recursive Remove Helper
template<typename K>
bool removeRecursive(Node*& node, const K& key) {
    if (!node) return false;

    if (key < node->key) return removeRecursive(node->left, key);
    else if (key > node->key) return removeRecursive(node->right, key);
    else { // Found the node to delete
        Node* toDelete = node;
        if (!node->left) node = node->right;
        else if (!node->right) node = node->left;
        else { // Two children
            Node*& predecessor = node->left;
            while (predecessor->right) predecessor = predecessor->right;
            // Swap values and delete the predecessor node
            std::swap(node->key, predecessor->key);
            // Recursively delete the swapped key from the left subtree
            return removeRecursive(node->left, key);
        }
        delete toDelete;
        return true;
    }
}

Applicasion Models: K-VS-KV

BSTs are foundational for associative containers, where data elements are interrelated by key.

1. K Model: Stores only keys. Useful for sets (e.g., a spell-checker dictionary).
2. KV Model: Stores key-value pairs. Useful for maps (e.g., word translation, frequency counters).

Converting the basic K-model BST to a KV-model involves modifying the node and insertion logic.

template<typename K, typename V>
struct KVNode {
    K key;
    V value;
    KVNode* left;
    KVNode* right;
    KVNode(const K& k, const V& v = V{}) : key(k), value(v), left(nullptr), right(nullptr) {}
};

template<typename K, typename V>
class KVTree {
    typedef KVNode<K, V> Node;
    Node* root;
    // ... (similar structure to BSTree)
public:
    // Insert or update
    bool insert(const K& key, const V& value = V{}) {
        // ... (find logic similar to BSTree::insert)
        if (current->key == key) {
            current->value = value; // Update existing value
            return false; // Indicate no new node was created
        }
        // ... (rest of insertion for new key)
    }
};

// Example: Word Frequency Counter
void countWords() {
    KVTree<std::string, int> freqCounter;
    std::vector<std::string> words = {"apple", "banana", "apple", "orange"};
    for (const auto& word : words) {
        auto node = freqCounter.find(word);
        if (node) {
            node->value++; // Increment count
        } else {
            freqCounter.insert(word, 1); // First occurrence
        }
    }
}

Key Tree Traversal Problems

Constructing a String from a Binary Tree (LeetCode 606): Generate a string representation using pre-order traversal, omitting unnecessary empty parentheses.

class Solution {
public:
    std::string tree2str(TreeNode* root) {
        if (!root) return "";
        std::string result = std::to_string(root->val);
        if (root->left || root->right) {
            result += "(" + tree2str(root->left) + ")";
        }
        if (root->right) {
            result += "(" + tree2str(root->right) + ")";
        }
        return result;
    }
};

Level Order Traversal (LeetCode 102): Return node values level by level. Use a queue, tracking the count of nodes at the current level.

class Solution {
public:
    std::vector<std::vector<int>> levelOrder(TreeNode* root) {
        std::vector<std::vector<int>> levels;
        if (!root) return levels;
        std::queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int levelSize = q.size();
            std::vector<int> currentLevel;
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front(); q.pop();
                currentLevel.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            levels.push_back(currentLevel);
        }
        return levels;
    }
};

Lowest Common Ancestor (LeetCode 236): Find the deepest node that is an ancestor of two given nodes. One approach is to find and compare paths from the root.

class Solution {
    bool findPath(TreeNode* root, TreeNode* target, std::vector<TreeNode*>& path) {
        if (!root) return false;
        path.push_back(root);
        if (root == target) return true;
        if (findPath(root->left, target, path) || findPath(root->right, target, path)) {
            return true;
        }
        path.pop_back();
        return false;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        std::vector<TreeNode*> pathP, pathQ;
        findPath(root, p, pathP);
        findPath(root, q, pathQ);
        TreeNode* lca = nullptr;
        for (size_t i = 0; i < std::min(pathP.size(), pathQ.size()); ++i) {
            if (pathP[i] == pathQ[i]) lca = pathP[i];
            else break;
        }
        return lca;
    }
};

Binary Search Tree to Sorted Doubly Linked List (LeetCode 426): Perform an in-order traversal, linking nodes as prev->right = current and current->left = prev.

class Solution {
    void convert(Node* node, Node*& prev) {
        if (!node) return;
        convert(node->left, prev);
        node->left = prev;
        if (prev) prev->right = node;
        prev = node;
        convert(node->right, prev);
    }
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return nullptr;
        Node* prev = nullptr;
        convert(root, prev);
        // Find head (leftmost) and tail (rightmost)
        Node* head = root;
        while (head->left) head = head->left;
        Node* tail = root;
        while (tail->right) tail = tail->right;
        // Make it circular
        head->left = tail;
        tail->right = head;
        return head;
    }
};

Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105): Use the first element of preorder as the root, find its position in inorder to partition left/right subtrees, and recurse.

class Solution {
    TreeNode* build(const std::vector<int>& pre, int& preIdx,
                    const std::vector<int>& in, int inLeft, int inRight) {
        if (inLeft > inRight) return nullptr;
        TreeNode* root = new TreeNode(pre[preIdx++]);
        int inRootIdx = inLeft;
        while (in[inRootIdx] != root->val) ++inRootIdx;
        root->left = build(pre, preIdx, in, inLeft, inRootIdx - 1);
        root->right = build(pre, preIdx, in, inRootIdx + 1, inRight);
        return root;
    }
public:
    TreeNode* buildTree(std::vector<int>& preorder, std::vector<int>& inorder) {
        int idx = 0;
        return build(preorder, idx, inorder, 0, inorder.size() - 1);
    }
};

Iterative Tree Traversals:

Pre-order (LeetCode 144): Visit node, push right child then left child to stack.

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stk;
    if (root) stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top(); stk.pop();
        result.push_back(node->val);
        if (node->right) stk.push(node->right);
        if (node->left) stk.push(node->left);
    }
    return result;
}

In-order (LeetCode 94): Traverse left, visit node, then traverse right.

vector<int> inorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stk;
    TreeNode* curr = root;
    while (curr || !stk.empty()) {
        while (curr) {
            stk.push(curr);
            curr = curr->left;
        }
        curr = stk.top(); stk.pop();
        result.push_back(curr->val);
        curr = curr->right;
    }
    return result;
}

Post-order (LeetCode 145): Track the last visited node to deterimne when to visit the current node.

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> result;
    stack<TreeNode*> stk;
    TreeNode* lastVisited = nullptr;
    TreeNode* node = root;
    while (node || !stk.empty()) {
        if (node) {
            stk.push(node);
            node = node->left;
        } else {
            TreeNode* peek = stk.top();
            if (peek->right && lastVisited != peek->right) {
                node = peek->right;
            } else {
                result.push_back(peek->val);
                lastVisited = peek;
                stk.pop();
            }
        }
    }
    return result;
}