Finding the Minimum Absolute Difference in a BST

Given the properties of a Binary Search Tree (BST), an in-order traversal processes nodes in ascending order of their values. Consequently, the smallest absolute difference between any two nodes in the tree must exist between two adjacent nodes in this sorted sequence. We can implement a recursive traversal that maintains a reference to the previously visited node to compute the difference on the fly.

void traverse(struct TreeNode* node, struct TreeNode** prev, int* minDiff) {
    if (!node) return;
    
    traverse(node->left, prev, minDiff);
    
    if (*prev != NULL) {
        int currentDiff = node->val - (*prev)->val;
        if (currentDiff < *minDiff) {
            *minDiff = currentDiff;
        }
    }
    *prev = node;
    
    traverse(node->right, prev, minDiff);
}

int getMinimumDifference(struct TreeNode* root) {
    int minDiff = INT_MAX;
    struct TreeNode* prev = NULL;
    traverse(root, &prev, &minDiff);
    return minDiff;
}

Finding Modes in a Binary Search Tree

To find all modes (elements with the highest frequency) in a BST, we can leverage the in-order traversal pattern which groups identical values together. By tracking the current value's frequency and comparing it with the maximum frequency found so far, we can dynamically update a result list. If the current frequency exceeds the maximum, we reset the list. If it equals the maximum, we append the current value.

void inorderSearch(struct TreeNode* node, int* currVal, int* currFreq, int* maxFreq, int* result, int* resSize) {
    if (!node) return;
    
    inorderSearch(node->left, currVal, currFreq, maxFreq, result, resSize);
    
    if (node->val == *currVal) {
        (*currFreq)++;
    } else {
        *currVal = node->val;
        *currFreq = 1;
    }
    
    if (*currFreq > *maxFreq) {
        *maxFreq = *currFreq;
        *resSize = 0;
        result[(*resSize)++] = node->val;
    } else if (*currFreq == *maxFreq) {
        result[(*resSize)++] = node->val;
    }
    
    inorderSearch(node->right, currVal, currFreq, maxFreq, result, resSize);
}

int* findMode(struct TreeNode* root, int* returnSize) {
    if (!root) {
        *returnSize = 0;
        return NULL;
    }
    int* result = (int*)malloc(sizeof(int) * 10001);
    int currVal = 0;
    int currFreq = 0;
    int maxFreq = 0;
    *returnSize = 0;
    
    inorderSearch(root, &currVal, &currFreq, &maxFreq, result, returnSize);
    return result;
}

Lowest Common Ancestor of a Binary Tree

The Lowest Common Ancestor (LCA) problem can be solved efficiently using a post-order traversal strategy (left-right-root). This approach naturally handles backtracking. The logic checks if the current node matches either target `p` or `q`. If both the left and right recursive calls return a non-null node, it indicates that the current root is the splitting point, hence the LCA. If only one side returns a non-null node, that node is propagated up, signifying that both targets are located within that specific subtree.

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, struct TreeNode* q) {
    if (root == NULL || root == p || root == q) {
        return root;
    }
    
    struct TreeNode* leftNode = lowestCommonAncestor(root->left, p, q);
    struct TreeNode* rightNode = lowestCommonAncestor(root->right, p, q);
    
    if (leftNode != NULL && rightNode != NULL) {
        return root;
    }
    
    return leftNode != NULL ? leftNode : rightNode;
}