# 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 | Item | Meaning | |---|---| | Input | Root of a valid BST | | Output | Minimum difference between any two different node values | | Tree size | At least `2` nodes | | Node values | All values are different | | Important property | Inorder traversal of a BST gives sorted values | Function shape: ```python class Solution: def minDiffInBST(self, root: Optional[TreeNode]) -> int: ... ``` ## Examples Example 1: ```text 4 / \ 2 6 / \ 1 3 ``` The inorder order is: ```python [1, 2, 3, 4, 6] ``` Adjacent differences are: ```python 2 - 1 = 1 3 - 2 = 1 4 - 3 = 1 6 - 4 = 2 ``` The minimum difference is: ```python 1 ``` Example 2: ```text 1 \ 48 / \ 12 49 ``` The inorder order is: ```python [1, 12, 48, 49] ``` Adjacent differences are: ```python 12 - 1 = 11 48 - 12 = 36 49 - 48 = 1 ``` The answer is: ```python 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: ```python 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: ```text 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: ```python [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: ```text left subtree -> current node -> right subtree ``` During traversal, we keep: | Variable | Meaning | |---|---| | `prev` | The previous value in sorted order | | `answer` | The smallest difference seen so far | 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: ```python 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: ```python 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 | Metric | Value | Why | |---|---|---| | Time | `O(n)` | Each node is visited once | | Space | `O(h)` | The recursion stack depends on tree height | 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 ```python # 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: ```python prev = None ``` There is no previous node before the first inorder node. We initialize the answer as infinity: ```python answer = float("inf") ``` Then we define an inorder traversal: ```python def inorder(node: Optional[TreeNode]) -> None: ``` The `nonlocal` statement lets the nested function update `prev` and `answer`: ```python nonlocal prev, answer ``` The base case handles empty children: ```python if node is None: return ``` First, visit smaller values: ```python inorder(node.left) ``` Then process the current node. If we have already seen a previous value, compute the adjacent difference: ```python if prev is not None: answer = min(answer, node.val - prev) ``` Then store the current value as the previous value for the next node: ```python prev = node.val ``` Finally, visit larger values: ```python inorder(node.right) ``` ## Testing ```python 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: | Test | Why | |---|---| | Balanced BST | Checks normal inorder behavior | | Right-heavy tree | Checks non-complete structure | | Two-node tree | Checks minimum allowed tree size | | Larger gap values | Confirms difference calculation |