LeetCode 783: Minimum Distance Between BST Nodes

Problem Restatement

We are given the root of a binary search tree.

We need to return the minimum difference between the values of any two different nodes.

Because the tree is a BST, an inorder traversal visits the node values in sorted order.

So instead of comparing every pair of nodes, we only need to compare neighboring values in inorder order.

Input and Output

Function shape:

class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        ...

Examples

Example 1:

      4
    /   \
   2     6
  / \
 1   3

The inorder order is:

[1, 2, 3, 4, 6]

Adjacent differences are:

2 - 1 = 1
3 - 2 = 1
4 - 3 = 1
6 - 4 = 2

The minimum difference is:

1

Example 2:

      1
       \
        48
       /  \
      12   49

The inorder order is:

[1, 12, 48, 49]

Adjacent differences are:

12 - 1 = 11
48 - 12 = 36
49 - 48 = 1

The answer is:

1

First Thought: Compare Every Pair

A direct solution is to collect all values from the tree, then compare every pair.

For each pair of values a and b, compute:

abs(a - b)

Then return the minimum result.

This works, but it ignores the BST property.

Problem With Pair Comparison

If the tree has n nodes, there are many pairs.

The number of pairs grows roughly like:

n * n

So this approach takes O(n^2) time.

We can do better because the tree is a binary search tree.

In sorted order, the minimum difference must occur between two adjacent values.

For example, in:

[1, 2, 3, 4, 6]

There is no need to compare 1 with 6.

Any non-adjacent pair has at least one value between them, so its difference cannot be smaller than all adjacent differences.

Key Insight

An inorder traversal of a BST gives values in ascending order.

So we traverse the tree in this order:

left subtree -> current node -> right subtree

During traversal, we keep:

Whenever we visit a node, we compare its value with prev.

Then we update prev to the current value.

Algorithm

1. Set prev = None.
2. Set answer = infinity.
3. Run inorder DFS.
4. When visiting a node:
   1. First visit its left subtree.
   2. Compare node.val with prev if prev exists.
   3. Update answer.
   4. Set prev = node.val.
   5. Visit its right subtree.
5. Return answer.

Correctness

An inorder traversal of a BST visits all node values in strictly increasing order.

Let the sorted values be:

v1, v2, v3, ..., vn

For any two non-adjacent values vi and vj, where i < j - 1, there is at least one value between them. Therefore:

vj - vi >= v(i + 1) - vi

So the minimum difference among all pairs must occur between two adjacent values in sorted order.

The algorithm visits the values in sorted order using inorder traversal. For every visited value, it compares that value with the previous visited value. Therefore, it checks every adjacent pair in sorted order.

Since the minimum pair must be adjacent in this order, and the algorithm checks all adjacent pairs, the algorithm returns the correct minimum difference.

Complexity

Here, n is the number of nodes and h is the height of the tree.

For a balanced BST, h = O(log n).

For a skewed BST, h = O(n).

Implementation

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        prev = None
        answer = float("inf")

        def inorder(node: Optional[TreeNode]) -> None:
            nonlocal prev, answer

            if node is None:
                return

            inorder(node.left)

            if prev is not None:
                answer = min(answer, node.val - prev)

            prev = node.val

            inorder(node.right)

        inorder(root)
        return answer

Code Explanation

We initialize the previous value as empty:

prev = None

There is no previous node before the first inorder node.

We initialize the answer as infinity:

answer = float("inf")

Then we define an inorder traversal:

def inorder(node: Optional[TreeNode]) -> None:

The nonlocal statement lets the nested function update prev and answer:

nonlocal prev, answer

The base case handles empty children:

if node is None:
    return

First, visit smaller values:

inorder(node.left)

Then process the current node.

If we have already seen a previous value, compute the adjacent difference:

if prev is not None:
    answer = min(answer, node.val - prev)

Then store the current value as the previous value for the next node:

prev = node.val

Finally, visit larger values:

inorder(node.right)

Testing

from typing import Optional

class TreeNode:
    def __init__(
        self,
        val: int = 0,
        left: Optional["TreeNode"] = None,
        right: Optional["TreeNode"] = None,
    ):
        self.val = val
        self.left = left
        self.right = right

def run_tests():
    s = Solution()

    root = TreeNode(
        4,
        TreeNode(2, TreeNode(1), TreeNode(3)),
        TreeNode(6),
    )
    assert s.minDiffInBST(root) == 1

    root = TreeNode(
        1,
        None,
        TreeNode(48, TreeNode(12), TreeNode(49)),
    )
    assert s.minDiffInBST(root) == 1

    root = TreeNode(2, TreeNode(1), None)
    assert s.minDiffInBST(root) == 1

    root = TreeNode(10, TreeNode(5), TreeNode(15))
    assert s.minDiffInBST(root) == 5

    print("all tests passed")

run_tests()

Test coverage: