Problem Description

You are given the root of a Binary Search Tree (BST). Your task is to find the minimum difference between the values of any two different nodes in the tree.

In other words, you need to look at all possible pairs of nodes in the BST and return the smallest absolute difference between their values.

For example, if you have a BST with nodes containing values [4, 2, 6, 1, 3], the differences between all pairs would include values like |4-2|=2, |4-6|=2, |4-1|=3, |4-3|=1, |2-1|=1, |2-3|=1, |2-6|=4, |6-1|=5, |6-3|=3, |1-3|=2. The minimum among all these differences is 1.

The key insight here is that in a BST, the inorder traversal gives us values in sorted order. When values are sorted, the minimum difference must occur between adjacent elements. Therefore, instead of checking all pairs, we can perform an inorder traversal and keep track of the minimum difference between consecutive nodes in the traversal sequence.

The solution uses a depth-first search (DFS) approach to perform inorder traversal (left → root → right). During traversal, it maintains a variable pre to store the previous node's value and calculates the difference between the current node's value and pre. The variable ans keeps track of the minimum difference found so far.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: A tree is a special type of graph (specifically, a connected acyclic graph). The BST in this problem is represented as a tree structure with nodes and edges (parent-child relationships).

Is it a tree?

• Yes: The problem explicitly states we're working with a Binary Search Tree (BST), which is a specialized tree data structure where each node has at most two children, and the left subtree contains values less than the node's value while the right subtree contains values greater than the node's value.

DFS

• Yes: Since we identified this as a tree problem, the flowchart directs us to use DFS (Depth-First Search).

Conclusion: The flowchart suggests using DFS for this tree problem. This aligns perfectly with our solution approach, which uses DFS to perform an inorder traversal of the BST. The inorder traversal is particularly useful here because it visits nodes in ascending order of their values in a BST, allowing us to efficiently find the minimum difference between consecutive values rather than checking all possible pairs.

Intuition

When we need to find the minimum difference between any two nodes in a BST, the naive approach would be to compare every node with every other node, which would take O(n²) time. However, we can leverage the special property of BSTs to optimize this.

The key insight comes from understanding what happens when we perform an inorder traversal on a BST: we get all values in sorted order. For example, if our BST contains values [4, 2, 6, 1, 3], an inorder traversal would give us [1, 2, 3, 4, 6].

Once we have a sorted sequence, finding the minimum difference becomes much simpler. In any sorted array, the minimum difference between any two elements must occur between adjacent elements. Why? Because as elements get farther apart in a sorted sequence, their difference only increases.

Consider the sorted sequence [1, 2, 3, 4, 6]:

• The difference between adjacent elements: |2-1|=1, |3-2|=1, |4-3|=1, |6-4|=2
• The minimum is 1

If we tried non-adjacent elements like |3-1|=2 or |6-1|=5, the differences would be larger.

This observation leads us to the solution strategy:

1. Perform an inorder traversal of the BST using DFS
2. During traversal, keep track of the previous node's value
3. Calculate the difference between the current node and the previous node
4. Keep updating the minimum difference found

By using DFS for inorder traversal and only comparing adjacent values in the sorted sequence, we reduce the problem from O(n²) comparisons to just O(n) comparisons, making it much more efficient.

Learn more about Tree, Depth-First Search, Breadth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The solution implements an inorder traversal using DFS (Depth-First Search) recursion. During the traversal, we maintain two important variables to track the minimum difference.

Data Structures and Variables:

• pre: Stores the value of the previously visited node in the inorder traversal. Initialized to -inf to handle the first node gracefully
• ans: Keeps track of the minimum difference found so far. Initialized to inf to ensure any valid difference will be smaller

Algorithm Implementation:

The dfs function follows the standard inorder traversal pattern:

1. Base Case: If the current node is None, return immediately
2. Left Subtree: Recursively traverse the left subtree with dfs(root.left)
3. Process Current Node:
   • Calculate the difference between current node's value and the previous node's value: root.val - pre
   • Update the minimum difference: ans = min(ans, root.val - pre)
   • Update pre to the current node's value for the next comparison: pre = root.val
4. Right Subtree: Recursively traverse the right subtree with dfs(root.right)

Why This Works:

Since we're doing an inorder traversal (left → root → right), nodes are visited in ascending order of their values. This means:

• When we visit a node, pre contains the value of the node with the largest value that's still smaller than the current node
• The difference root.val - pre gives us the minimum possible difference for the current node with any smaller-valued node
• By tracking the minimum of all such differences, we find the global minimum difference

Use of nonlocal:

The nonlocal keyword is used to modify the pre and ans variables that are defined in the outer function scope. This allows the recursive dfs function to maintain state across all recursive calls.

Time and Space Complexity:

• Time: O(n) where n is the number of nodes, as we visit each node exactly once
• Space: O(h) where h is the height of the tree, due to the recursion call stack

Example Walkthrough

Let's walk through the solution with a small BST example:

       4
      / \
     2   6
    / \
   1   3

We'll trace through the inorder traversal DFS to see how we find the minimum difference.

Initial State:

• pre = -inf (no previous node visited yet)
• ans = inf (no minimum found yet)

Step 1: Start DFS from root (4)

• Call dfs(4)
• First, traverse left subtree: dfs(2)

Step 2: At node 2

• Call dfs(2)
• First, traverse left subtree: dfs(1)

Step 3: At node 1 (leftmost node)

• Call dfs(1)
• Left child is None, so continue
• Process node 1:
  • Calculate difference: 1 - (-inf) = inf
  • Update ans: ans = min(inf, inf) = inf
  • Update pre: pre = 1
• Right child is None, return

Step 4: Back at node 2

• Left subtree done, process node 2:
  • Calculate difference: 2 - 1 = 1
  • Update ans: ans = min(inf, 1) = 1
  • Update pre: pre = 2
• Traverse right subtree: dfs(3)

Step 5: At node 3

• Call dfs(3)
• Left child is None
• Process node 3:
  • Calculate difference: 3 - 2 = 1
  • Update ans: ans = min(1, 1) = 1
  • Update pre: pre = 3
• Right child is None, return

Step 6: Back at root node 4

• Left subtree done, process node 4:
  • Calculate difference: 4 - 3 = 1
  • Update ans: ans = min(1, 1) = 1
  • Update pre: pre = 4
• Traverse right subtree: dfs(6)

Step 7: At node 6

• Call dfs(6)
• Left child is None
• Process node 6:
  • Calculate difference: 6 - 4 = 2
  • Update ans: ans = min(1, 2) = 1
  • Update pre: pre = 6
• Right child is None, return

Final Result: The minimum difference is 1

The inorder traversal visited nodes in order: [1, 2, 3, 4, 6], and we checked differences between consecutive pairs: (1,2)→1, (2,3)→1, (3,4)→1, (4,6)→2. The minimum is 1.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm performs an in-order traversal of the binary search tree using depth-first search (DFS). Each node in the tree is visited exactly once during the traversal. The operations performed at each node (comparison with min() and variable updates) take constant time O(1). Therefore, the overall time complexity is O(n), where n is the total number of nodes in the binary search tree.

Space Complexity: O(n)

The space complexity is determined by the recursive call stack used during the DFS traversal. In the worst case, when the tree is completely unbalanced (essentially a linked list), the recursion depth can reach n levels deep, requiring O(n) space on the call stack. In the best case of a perfectly balanced tree, the recursion depth would be O(log n), but we consider the worst-case scenario for space complexity analysis. Additionally, the algorithm uses only a constant amount of extra space for the variables pre and ans, which doesn't affect the overall space complexity. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow with Initial Values

One common pitfall is using language-specific maximum/minimum integer values instead of infinity. In some programming languages, using Integer.MAX_VALUE or Integer.MIN_VALUE might cause overflow issues when performing arithmetic operations.

Problem Example:

# Potentially problematic in some languages
previous_value = -sys.maxsize  # Could overflow when subtracting
minimum_difference = sys.maxsize

Solution: Use floating-point infinity which handles arithmetic operations safely:

from math import inf
previous_value = -inf
minimum_difference = inf

2. Forgetting to Handle the First Node

A critical pitfall is not properly initializing previous_value. If you initialize it to 0 or any arbitrary value, you might get incorrect results.

Problem Example:

previous_value = 0  # Wrong! This could give incorrect difference for first node
# If first inorder node has value 100, difference would be 100-0=100

Solution: Initialize previous_value to negative infinity so the first comparison is effectively skipped:

previous_value = -inf  # Ensures first node's difference is infinity (ignored)

3. Using Global Variables Instead of Nonlocal

Attempting to modify outer scope variables without the nonlocal keyword will create new local variables instead, causing the function to not work correctly.

Problem Example:

def minDiffInBST(self, root):
    previous_value = -inf
    minimum_difference = inf
  
    def inorder_traversal(node):
        if node is None:
            return
        inorder_traversal(node.left)
        # This creates NEW local variables, doesn't modify outer ones!
        minimum_difference = min(minimum_difference, node.val - previous_value)
        previous_value = node.val
        inorder_traversal(node.right)

Solution: Always declare nonlocal for variables you need to modify:

def inorder_traversal(node):
    if node is None:
        return
    inorder_traversal(node.left)
  
    nonlocal previous_value, minimum_difference  # Essential!
    minimum_difference = min(minimum_difference, node.val - previous_value)
    previous_value = node.val
  
    inorder_traversal(node.right)

4. Comparing All Pairs Instead of Adjacent Values

A conceptual pitfall is trying to compare every node with every other node, leading to O(n²) complexity.

Problem Example:

# Inefficient approach - checking all pairs
def minDiffInBST(self, root):
    values = []
    def collect(node):
        if node:
            values.append(node.val)
            collect(node.left)
            collect(node.right)
  
    collect(root)
    min_diff = inf
    for i in range(len(values)):
        for j in range(i+1, len(values)):
            min_diff = min(min_diff, abs(values[i] - values[j]))
    return min_diff

Solution: Leverage BST property - inorder traversal gives sorted values, so minimum difference must be between adjacent elements:

# Efficient - only check adjacent values in sorted order
def inorder_traversal(node):
    # ... inorder traversal comparing only consecutive values