A Binary Search Tree (BST) maintains a hierarchical order where every node satisfies specific ordering constraints relative to its children. For any given node, values in the left subtree are smaller than the node's key, and values in the right subtree are larger. Both subtrees must also adhere to these recursive rules.

Computing Minimum Absolute Difference

When calculating the smallest numerical gap within a BST, the optimal approach utilizes the fact that an in-order traversal produces a sorted sequence. Consequently, the minimum difference always exists between two consecutive elements in this sequence.

Method: Single Pass In-Order Traversal Maintain a reference to the previously visited node. During the traversal, compute the difference between the current node and the predecessor.

class Solution {
private:
    TreeNode* parentNode = nullptr;
    int minimumGap = 2147483647; 

    void visitTree(TreeNode* root) {
        if (!root) return;

        visitTree(root->left);

        if (parentNode) {
            int diff = root->val - parentNode->val;
            if (diff < minimumGap) {
                minimumGap = diff;
            }
        }
        parentNode = root;
        
        visitTree(root->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        visitTree(root);
        return minimumGap;
    }
};

Alternatively, one could store all values in a vector and iterate through them. However, the single-pass pointer method is space-efficient as it avoids auxiliary storage proportional to the tree size.

Finding the Mode Values

To identify the most frequently occurring number(s) in a BST, leverage the property that duplicate values appear contiguously during an in-order walk. You must track the current run length of identical values and compare it against the highest frequency observed so far.

Algorithm: Frequency Tracking Iterate through the sorted sequence generated by traversal. Update the mode list whenever a higher frequency is discovered, clearing previous results.

class Solution {
private:
    int currentFreq = 0;
    int maxFreq = 0;
    TreeNode* prevNode = nullptr;
    std::vector<int> modeList;

    void analyzeTree(TreeNode* node) {
        if (!node) return;

        analyzeTree(node->left);

        if (prevNode) {
            if (node->val == prevNode->val) {
                currentFreq++;
            } else {
                currentFreq = 1;
            }
        } else {
            currentFreq = 1;
        }
        prevNode = node;

        if (currentFreq > maxFreq) {
            maxFreq = currentFreq;
            modeList.clear();
            modeList.push_back(node->val);
        } else if (currentFreq == maxFreq) {
            modeList.push_back(node->val);
        }

        analyzeTree(node->right);
    }

public:
    std::vector<int> findMode(TreeNode* root) {
        currentFreq = 0;
        maxFreq = 0;
        prevNode = nullptr;
        modeList.clear();
        analyzeTree(root);
        return modeList;
    }
};

Ensure the list is cleared correctly when a new maximum frequency is found to prevent stale data from persisting in the result collection.

Resolving Lowest Common Ancestor

Locating the Lowest Common Ancestor (LCA) in a binary tree requires processing the tree from the bottom up. This necessitates a post-order traversal strategy to determine if child sub-trees contain the target nodes.

Logic Flow Recursively search for the target nodes p and q. If the current node matches either target, return it. If both recursive calls return non-null pointers, the current node is the divergence point (LCA). If only one call returns a valid node, propagate that result upward.

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || root == p || root == q) {
            return root;
        }

        TreeNode* leftResult = lowestCommonAncestor(root->left, p, q);
        TreeNode* rightResult = lowestCommonAncestor(root->right, p, q);

        if (leftResult && rightResult) {
            return root;
        }

        return (leftResult != nullptr) ? leftResult : rightResult;
    }
};

This approach ensures that once a common ancestor is identified, the recursion unwinds correctly without unnecessary re-examinaiton of upper branches.

Core Technical Insights

Post-order traversal is essential for problems requiring state aggregation from leaf nodes back to the root. Conversely, BST operations frequently benefit from in-order processing to exploit the inherent sorting of keys. Managing state such as previous nodes or frequencies effectively during recursion often eliminates the need for global arrays or excessive data structure allocations.