783. Minimum Distance between BST Nodes - Explanation

1. Brute Force (DFS)

Intuition

The most straightforward approach is to compare every pair of nodes in the tree. For each node, we traverse the entire tree to find the minimum absolute difference between this node's value and any other node's value. While simple to understand, this approach doesn't leverage the BST property and results in redundant comparisons.

Algorithm

Define a helper function dfs(node) that returns the minimum difference involving any node in the subtree rooted at node.
For each node visited, call another helper dfs1(root, node) that traverses the entire tree and computes the minimum difference between node and every other node.
Recursively compute the minimum for left and right subtrees.
Return the overall minimum difference found.

# 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:
        def dfs(node):
            if not node:
                return float("inf")
            res = dfs1(root, node)
            res = min(res, dfs(node.left))
            res = min(res, dfs(node.right))
            return res

        def dfs1(root, node):
            if not root:
                return float("inf")

            res = float("inf")
            if root != node:
                res = abs(root.val - node.val)
            res = min(res, dfs1(root.left, node))
            res = min(res, dfs1(root.right, node))
            return res

        return dfs(root)

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Inorder Traversal

Intuition

In a BST, an inorder traversal visits nodes in sorted order. The minimum difference between any two nodes must occur between consecutive elements in this sorted sequence. So we perform an inorder traversal to collect all values into an array, then scan through the array to find the minimum difference between adjacent elements.

Algorithm

Perform an inorder traversal (left, root, right) and collect all node values into an array.
The array is now sorted in ascending order.
Iterate through the array and compute the difference between each pair of adjacent elements.
Track and return the minimum difference found.

# 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:
        arr = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            arr.append(node.val)
            dfs(node.right)

        dfs(root)
        res = arr[1] - arr[0]
        for i in range(2, len(arr)):
            res = min(res, arr[i] - arr[i - 1])
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Inorder Traversal (Space Optimized)

Intuition

Instead of storing all values in an array and then finding the minimum difference, we can compute the answer during the traversal itself. We keep track of the previously visited node during the inorder walk. At each step, we compare the current node's value with the previous node's value (since they are consecutive in sorted order) and update the minimum difference on the fly.

Algorithm

Maintain a prev pointer to track the previously visited node during inorder traversal.
Initialize res to infinity.
Perform inorder traversal:
- Recurse on the left subtree.
- If prev exists, update res with min(res, current.val - prev.val).
- Set prev to the current node.
- Recurse on the right subtree.
Return res.

# 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, res = None, float("inf")

        def dfs(node):
            nonlocal prev, res
            if not node:
                return

            dfs(node.left)
            if prev:
                res = min(res, node.val - prev.val)
            prev = node
            dfs(node.right)

        dfs(root)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

4. Iterative DFS (Inorder Traversal)

Intuition

The recursive inorder traversal can be converted to an iterative version using an explicit stack. This avoids recursion overhead and gives us more control over the traversal. The logic remains the same: we visit nodes in sorted order and compare each node with its predecessor.

Algorithm

Initialize an empty stack and set cur to the root. Maintain prev to track the previous node.
While the stack is not empty or cur is not null:
- Push all left descendants of cur onto the stack.
- Pop a node from the stack.
- If prev exists, update the minimum difference.
- Set prev to the current node and move cur to the right child.
Return the minimum difference found.

# 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:
        stack, prev, res = [], None, float("inf")
        cur = root

        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left

            cur = stack.pop()
            if prev:
                res = min(res, cur.val - prev.val)
            prev = cur
            cur = cur.right

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Morris Traversal

Intuition

Morris traversal allows us to perform inorder traversal without using a stack or recursion, achieving O(1) extra space. The idea is to temporarily modify the tree by creating links from predecessor nodes back to their successors, allowing us to navigate the tree without additional memory. We traverse the tree, comparing consecutive values as before.

Algorithm

Initialize cur to the root and prevVal to track the value of the previous node visited.
While cur is not null:
- If cur has no left child:
  - Process cur (compare with prevVal and update minimum).
  - Update prevVal and move to the right child.
- Else, find the inorder predecessor (rightmost node in left subtree):
  - If the predecessor's right pointer is null, set it to cur and move left.
  - If the predecessor's right pointer is cur, restore it to null, process cur, update prevVal, and move right.
Return the minimum difference found.

# 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:
        prevVal = res = float("inf")
        cur = root

        while cur:
            if not cur.left:
                if prevVal != float("inf"):
                    res = min(res, cur.val - prevVal)
                prevVal = cur.val
                cur = cur.right
            else:
                prev = cur.left
                while prev.right and prev.right != cur:
                    prev = prev.right

                if not prev.right:
                    prev.right = cur
                    cur = cur.left
                else:
                    prev.right = None
                    if prevVal != float("inf"):
                        res = min(res, cur.val - prevVal)
                    prevVal = cur.val
                    cur = cur.right

        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Not Leveraging BST Properties

The most common mistake is treating this as a generic binary tree problem and comparing all pairs of nodes, resulting in O(n^2) time complexity. The BST property guarantees that inorder traversal produces a sorted sequence, so the minimum difference must occur between consecutive elements. Always use inorder traversal to reduce complexity to O(n).

Comparing Non-Adjacent Elements

In a sorted sequence, the minimum difference is always between adjacent elements. Some implementations incorrectly compare non-adjacent pairs or track global minimum/maximum values instead of the previous node, missing the optimal answer or overcomplicating the solution.