Minimum Absolute Difference in BST - Solution & Explanation

Problem Overview: You are given the root of a Binary Search Tree and must return the minimum absolute difference between values of any two different nodes. Because the tree follows BST ordering rules, an efficient solution relies on processing node values in sorted order.

Approach 1: In-order Traversal Using Stack (Time: O(n), Space: O(h))

A Binary Search Tree produces values in sorted order when visited using in-order traversal (left → node → right). Instead of recursion, this approach uses an explicit stack to simulate the traversal. As you iterate through nodes, track the value of the previously visited node. The minimum absolute difference must occur between two adjacent values in the sorted sequence, so compute current.val - prev at each step and update the minimum.

The algorithm repeatedly pushes left children onto the stack, pops the next node to process, then moves to the right subtree. Each node is visited exactly once. This makes the time complexity O(n), where n is the number of nodes. The stack stores at most the height of the tree, giving O(h) auxiliary space. Use this version when you want an iterative solution or when recursion depth might be a concern.

Approach 2: Recursive In-order Traversal (Time: O(n), Space: O(h))

This version performs the same sorted traversal but relies on recursion instead of a manual stack. The recursion explores the left subtree, processes the current node, then explores the right subtree. Maintain two variables across calls: the previously visited value and the global minimum difference. Each time the traversal visits a node, compare it with the previous value and update the minimum difference.

The key insight is identical: in a BST, the smallest difference always occurs between two consecutive values in the sorted in-order sequence. Because each node is visited once, the runtime is O(n). The recursion stack grows up to the tree height, so space complexity is O(h). This version is concise and commonly used in interview explanations when discussing Depth-First Search on trees.

Both approaches rely on the ordering property of a tree structured as a BST. Instead of comparing every pair of nodes, which would take O(n²), you only compare neighbors in the sorted traversal order.

Recommended for interviews: The recursive in-order traversal is the most common explanation because it clearly demonstrates how BST ordering reduces the problem to comparing adjacent values. Interviewers often accept either version, but showing the stack-based implementation proves you understand how recursion works under the hood.