https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/?envType=study-plan-v2&envId=top-interview-150

Approach 3: In-order Traversal Without List

Algorithm

1. Create an answer variable minDifference and initialize it to infinity.
2. Create a TreeNode variable prevNode to keep track of the previous node we have traversed. Initialize it to null.
3. Perform the inorder traversal of the binary search tree (BST). Call inorderTraversal(root) where inorderTraversal is a recursive method that takes TreeNode node as a parameter. We perform the following in this method:
   • If node is null, return.
   • Recursively perform the in-order traversal for node.left.
   • We handle node now. We check its difference with the previously visited node prevNode. If prevNode != null, it means we have visited a node previously and hence, we try to update minDifference using minDifference = min(minDifference, node.val - prevNode.val).
   • Recursively perform the in-order traversal for node.right.
4. Return minDifference.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDifference = INT_MAX;
    TreeNode* prevNode;

    void inorderTraversal(TreeNode* node){
        if (node == NULL) { return; }

        inorderTraversal(node->left);
        // Find the difference with the previous value if it is there
        if(prevNode != NULL){
            minDifference = min(minDifference, node->val - prevNode->val);
        }
        prevNode = node;
        inorderTraversal(node->right);
    }

    int getMinimumDifference(TreeNode* root) {
        inorderTraversal(root);
        return minDifference;
    }
};

Complexity Analysis

Here, $n$ is the number of nodes in the given binary search tree.

• Time complexity: $O(n)$
  • We traverse once over each node of the BST using in-order traversal which takes $O(n)$ time.
• Space complexity: O(n)
  • The in-order traversal is recursive and would take some space to store the stack calls. The maximum number of active stack calls at a time would be the tree's height, which in the worst case would be $O(n)$ when the tree is a straight line.
  • Note that this space complexity is only for the worst-case scenario, and in the average case we have greatly improved our space complexity since we don't need to create a list to store all the nodes.