Minimum Distance Between BST Nodes: Inorder Traversal

You are given the root of a Binary Search Tree. Return the minimum difference between the values of any two different nodes in the tree.

This is LeetCode 783: Minimum Distance Between BST Nodes. The key insight is that in a BST, an inorder traversal produces values in sorted order, and the minimum difference between any two nodes must occur between two consecutive values in that sorted sequence.

Why this problem matters

If you try to compare every pair of nodes, you end up with an O(n^2) solution. But a BST gives you a powerful property for free: inorder traversal visits nodes in ascending order. That means the values come out sorted without you having to sort anything.

Once you have a sorted sequence, the minimum difference between any two elements must be between two adjacent elements. Think about it: if you have values [1, 3, 5], the smallest gap is between 1 and 3 (which is 2), not between 1 and 5 (which is 4). Skipping over a middle element can only make the difference larger, never smaller.

So the problem reduces to: do an inorder traversal, and at each step compare the current node's value with the previous node's value. Track the smallest difference you see. That is the answer.

The approach: inorder traversal

The plan is simple. Perform a recursive inorder traversal of the BST. As you visit each node, check if there is a previous value. If there is, compute the difference between the current value and the previous value, and update the running minimum. Then set the current value as the new previous value and continue.

You do not need to store the entire sorted list. You only need to remember the last value you visited, because the minimum difference is always between consecutive values.

def min_diff_in_bst(root):
    prev = [None]
    result = [float('inf')]

    def inorder(node):
        if not node:
            return
        inorder(node.left)
        if prev[0] is not None:
            result[0] = min(result[0], node.val - prev[0])
        prev[0] = node.val
        inorder(node.right)

    inorder(root)
    return result[0]

Let's break this down:

• prev = [None] and result = [float('inf')] use lists so the inner function can modify them. prev tracks the last visited node's value, and result holds the smallest difference found so far.
• inorder(node.left) recurses into the left subtree first. This ensures we visit smaller values before larger ones.
• if prev[0] is not None checks whether we have a previous value to compare against. The very first node visited has no predecessor.
• node.val - prev[0] works because inorder traversal of a BST always yields ascending values. The current value is always greater than or equal to the previous value, so the difference is never negative.
• inorder(node.right) recurses into the right subtree after processing the current node.

Step-by-step walkthrough

Let's trace the algorithm through the BST [4, 2, 6, 1, 3]. Watch how the inorder traversal visits nodes in sorted order, and the minimum difference gets tracked at each step.

The traversal visits nodes in the order 1, 2, 3, 4, 6. At node 1, there is no previous value, so we skip the comparison. At node 2, the difference from 1 is 1. At node 3, the difference from 2 is 1. At node 4, the difference from 3 is 1. At node 6, the difference from 4 is 2. The minimum across all these comparisons is 1, which is our answer.

Notice that we never needed to store the full sorted array. We only kept track of the single previous value, which is enough to compute consecutive differences on the fly.

Complexity analysis

Where h is the height of the tree.

Time is O(n) because we visit every node exactly once. At each node, we do O(1) work: one comparison, one subtraction, and one min operation.

Space is O(h) where h is the height of the tree. This is the depth of the recursion stack. For a balanced BST, h = log n. For a completely skewed tree (like a linked list), h = n.

Edge cases to watch for

• Two nodes only: the tree has exactly two nodes, so the answer is simply the absolute difference between the root and its single child. The algorithm handles this naturally since there is exactly one consecutive pair.
• Skewed tree (all left or all right children): the BST degenerates into a sorted linked list. Inorder traversal still works correctly, but the recursion stack depth becomes O(n) instead of O(log n).
• All nodes equally spaced: for example, values [2, 4, 6, 8]. Every consecutive difference is the same, so the algorithm returns that common difference.

The building blocks

This problem is built on one fundamental building block:

BST inorder traversal property (bst-inorder-property). An inorder traversal of a BST visits nodes in ascending sorted order. This means any problem that requires sorted values from a BST can be solved by performing an inorder traversal and processing values as they appear. The skeleton looks like this:

def process_bst(root):
    prev = [None]

    def inorder(node):
        if not node:
            return
        inorder(node.left)
        # process node.val using prev[0]
        prev[0] = node.val
        inorder(node.right)

    inorder(root)

For Minimum Distance Between BST Nodes, the "process" step computes node.val - prev[0] and tracks the minimum. For Validate Binary Search Tree, the "process" step checks that node.val > prev[0]. For Minimum Absolute Difference in BST, it is the exact same problem with the same solution. This pattern appears in many BST problems where you need to reason about the sorted relationship between node values.

From understanding to recall

You just walked through a clean solution that uses inorder traversal to get sorted values from a BST, then tracks the minimum difference between consecutive values. The key insight, that the minimum difference must be between consecutive values in sorted order, is something you understand right now.

But in an interview, will you remember to use inorder traversal instead of trying all pairs? Will you remember that you only need to track the previous value, not build the entire sorted list? These details slip away faster than you think.

Spaced repetition locks them in. You practice writing the solution from scratch at increasing intervals. First after a day, then three days, then a week. Each time, you reconstruct the inorder skeleton, the prev tracking, and the min update from memory. After a few repetitions, the BST inorder property pattern becomes automatic, and you can apply it to any BST problem that needs sorted order.

Related posts

• Binary Tree Inorder Traversal - The core traversal technique used here
• Validate Binary Search Tree - Another BST property problem using inorder traversal
• Minimum Absolute Difference in BST - Essentially the same problem