LeetCode 783 - Minimum Distance Between BST Nodes

The problem asks us to find the minimum difference between values of any two nodes in a Binary Search Tree (BST). In other words, given a BST, we need to calculate the smallest absolute difference a - b where a and b are values of two distinct nodes.

leetcodeeasytreedepth-first-searchbreadth-first-searchbinary-search-treebinary-tree

LeetCode Problem 783

Difficulty: 🟢 Easy
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem asks us to find the minimum difference between values of any two nodes in a Binary Search Tree (BST). In other words, given a BST, we need to calculate the smallest absolute difference |a - b| where a and b are values of two distinct nodes. The input is the root of the BST, which is guaranteed to have at least two nodes, and all node values lie in the range [0, 10^5].

Since the input is a BST, we know that the left child of a node contains smaller values, and the right child contains larger values. This property is crucial because it implies that an in-order traversal of the BST will produce values in strictly increasing order. Therefore, the minimum difference must occur between two consecutive values in this sorted in-order sequence.

Important edge cases include very small trees with just two nodes, trees where all nodes are in a straight line (either all left children or all right children), and trees with duplicate values (though duplicates are not explicitly restricted in this problem).

Approaches

Brute-Force Approach

The naive approach would be to traverse all pairs of nodes in the tree, compute the absolute difference for each pair, and then return the minimum difference. This guarantees correctness because it considers all possible pairs, but it is inefficient. For n nodes, there are n * (n-1) / 2 pairs, resulting in a time complexity of O(n²). Space complexity is O(n) if we store all node values in a list.

Optimal Approach

The key insight comes from the BST property: an in-order traversal produces nodes in sorted order. Once we have a sorted sequence of node values, the minimum difference must occur between two consecutive elements. This reduces the problem to a linear scan of the in-order sequence, giving an O(n) time complexity and O(h) space complexity if we use recursion, where h is the height of the tree (O(log n) for balanced, O(n) for skewed). We do not need to compare every pair, only consecutive elements.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Compare all pairs of nodes
Optimal O(n) O(h) In-order traversal and check consecutive differences

Algorithm Walkthrough

  1. Initialize two variables: prev to store the previous node value in in-order traversal and min_diff to store the current minimum difference. Start prev as None and min_diff as infinity.

  2. Perform an in-order traversal recursively. For each node:

  3. Traverse the left subtree.

  4. If prev is not None, compute the difference between the current node value and prev, and update min_diff if the difference is smaller.

  5. Update prev to the current node value.

  6. Traverse the right subtree.

  7. After traversal, min_diff holds the minimum absolute difference between any two nodes.

Why it works: In-order traversal guarantees sorted order of BST values. The minimum difference must occur between two consecutive values in sorted order. By only comparing consecutive values, we ensure the correct minimum is found efficiently.

Python Solution

# 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
from typing import Optional

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

        def inorder(node: Optional[TreeNode]):
            if not node:
                return
            inorder(node.left)
            if self.prev is not None:
                self.min_diff = min(self.min_diff, node.val - self.prev)
            self.prev = node.val
            inorder(node.right)
        
        inorder(root)
        return self.min_diff

Explanation: We define a recursive inorder function to traverse the tree. For each node, we first explore the left child, then compute the difference with prev if it exists, update min_diff, and finally update prev to the current node. The traversal ensures all nodes are visited in sorted order.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDiffInBST(root *TreeNode) int {
    var prev *int
    minDiff := 1 << 31 - 1  // Max int

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }
        inorder(node.Left)
        if prev != nil {
            diff := node.Val - *prev
            if diff < minDiff {
                minDiff = diff
            }
        }
        prev = &node.Val
        inorder(node.Right)
    }

    inorder(root)
    return minDiff
}

Explanation: In Go, we use a pointer prev to track the previous node value. We use a recursive in-order traversal to maintain sorted order. The logic mirrors the Python implementation, with explicit pointer handling to accommodate Go's value semantics.

Worked Examples

Example 1: root = [4,2,6,1,3]

In-order traversal: 1, 2, 3, 4, 6

Node prev min_diff
1 None inf
2 1 1
3 2 1
4 3 1
6 4 1

Output: 1

Example 2: root = [1,0,48,null,null,12,49]

In-order traversal: 0, 1, 12, 48, 49

Node prev min_diff
0 None inf
1 0 1
12 1 1
48 12 1
49 48 1

Output: 1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each node is visited exactly once in in-order traversal
Space O(h) Recursion stack depth equals tree height h

Since the tree is a BST, recursion stack space depends on the height. For balanced trees, O(log n); for skewed trees, O(n).

Test Cases

# Basic examples
assert Solution().minDiffInBST(TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))) == 1  # Example 1
assert Solution().minDiffInBST(TreeNode(1, TreeNode(0), TreeNode(48, TreeNode(12), TreeNode(49)))) == 1  # Example 2

# Smallest tree possible
assert Solution().minDiffInBST(TreeNode(1, None, TreeNode(2))) == 1  # Two nodes only

# Skewed tree (all right)
assert Solution().minDiffInBST(TreeNode(1, None, TreeNode(3, None, TreeNode(5)))) == 2

# Skewed tree (all left)
assert Solution().minDiffInBST(TreeNode(5, TreeNode(3, TreeNode(1)))) == 2

# Duplicate values (edge case if allowed)
assert Solution().minDiffInBST(TreeNode(2, TreeNode(2), TreeNode(4))) == 0
Test Why
Example 1 Standard BST with multiple levels
Example 2 BST with null children and larger values
Smallest tree Minimal input, edge case
Skewed right Tests linear BST structure
Skewed left Tests linear BST structure
Duplicates Ensures zero difference is handled correctly

Edge Cases

One edge case is a tree with only two nodes. Since the algorithm relies on differences between consecutive nodes in in-order traversal, it correctly handles this case by computing the difference directly.

Another edge case is a skewed tree, where all nodes are either left or right children. This tests that recursion handles extreme heights and does not incorrectly assume a balanced structure.

A third edge case is having duplicate node values. Even though the problem does not explicitly forbid duplicates, our algorithm correctly returns 0 as the minimum difference if two nodes have the same value, which is the mathematically correct minimum.

This implementation gracefully handles all these edge cases by leveraging in-order traversal and comparing consecutive values only.