Minimal Absolute Difference in BST

Since an in-order traversal of a binary search tree produces a sorted sequence, the smallest absolute difference between any two nodes corresponds to the minimal gap between adjacent elements in this sequence. The strategy involves tracking the previously visited node and comparing its value with the current node during the traversal. This eliminates the need to compare every pair of nodes.

class Solution {
public:
    TreeNode* prevNode = nullptr;
    int minDiff = 2147483647;
    
    int getMinimumDifference(TreeNode* root) {
        if (!root) return minDiff;
        
        getMinimumDifference(root->left);
        
        if (prevNode != nullptr) {
            int diff = std::abs(prevNode->val - root->val);
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
        prevNode = root;
        
        getMinimumDifference(root->right);
        return minDiff;
    }
};

Identifying Modes in Binary Search Tree

Multiple elements may share the maximum frequency in the dataset. Because the BST yields a sorted order via in-order traversal, identical values appear consecutive. We iterate through this sorted stream, maintaining a running count of the current value. If the current frequency surpasses the established maximum, we update the limit and restart the result collection. When the frequency matches the maximum, we simply extend the existing collection.

class Solution {
private:
    TreeNode* lastVisited = nullptr;
    int currentCount = 0;
    int maxFrequency = 0;
    std::vector<int> modes;
    
    void inorderTraversal(TreeNode* node) {
        if (!node) return;
        
        inorderTraversal(node->left);
        
        if (!lastVisited) {
            currentCount = 1;
        } else if (lastVisited->val == node->val) {
            currentCount++;
        } else {
            currentCount = 1;
        }
        
        lastVisited = node;
        
        if (currentCount > maxFrequency) {
            maxFrequency = currentCount;
            modes.clear();
            modes.push_back(node->val);
        } else if (currentCount == maxFrequency) {
            modes.push_back(node->val);
        }
        
        inorderTraversal(node->right);
    }
    
public:
    std::vector<int> findMode(TreeNode* root) {
        inorderTraversal(root);
        return modes;
    }
};

Locating the Lowest Common Ancestor

Determining the shared ancestor requires evaluating the status of subtrees before resolving the current node's decision. A post-order recursive approach effectively gathers information from children upwards. The base case handles empty nodes or direct matches to the target nodes. The logic then determines whether the common ancestor resides in the left subtree, right subtree, or is the current node itself based on non-null returns from both sides.