Minimum Distance Between BST Nodes - Solution & Explanation

Problem Overview: Given the root of a Binary Search Tree (BST), compute the minimum absolute difference between values of any two different nodes. Because of the BST property, an inorder traversal visits nodes in sorted order, which makes it easy to compare adjacent values.

Approach 1: Inorder Traversal (O(n) time, O(h) space)

The key BST property: inorder traversal returns values in ascending order. Instead of comparing every pair of nodes, you only compare each node with the previously visited node during traversal. Keep a variable prev to store the previous value and update the minimum difference using current - prev. Traverse the tree using DFS recursion or an explicit stack. This reduces the problem from pairwise comparisons to a single pass over the sorted sequence of values.

This approach uses a standard Depth-First Search traversal on a Binary Search Tree. The time complexity is O(n) because each node is visited once. Space complexity is O(h), where h is the tree height, due to the recursion stack (O(log n) for balanced trees, O(n) for skewed trees).

Approach 2: Morris Traversal (O(n) time, O(1) space)

Morris Traversal performs inorder traversal without recursion or a stack by temporarily modifying tree pointers. For each node, locate its inorder predecessor (the rightmost node in its left subtree). Create a temporary thread pointing back to the current node so the traversal can return after finishing the left subtree.

While visiting nodes in inorder order, maintain the same prev value and update the minimum difference exactly as in the standard traversal. After processing, restore the tree structure by removing the temporary threads. This approach keeps the O(n) time complexity but reduces auxiliary space to O(1).

Morris traversal is useful when memory constraints matter or when recursion depth could become large. The logic is more complex than the standard DFS approach but eliminates the stack entirely while still leveraging the sorted order property of a Tree that satisfies BST ordering.

Recommended for interviews: The inorder traversal solution is what interviewers typically expect. It directly uses the BST property and is easy to implement with DFS. Mentioning Morris traversal shows deeper understanding of tree traversal techniques and space optimization, but most interviewers prioritize the clear O(n) DFS solution first.