Problem Description

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

In other words, you need to:

1. Look at all possible pairs of nodes in the BST
2. Calculate the absolute difference between their values
3. Return the smallest difference found

For example, if you have a BST with nodes containing values like 4, 2, 6, 1, and 3, you would compare all pairs:

• |4-2| = 2
• |4-6| = 2
• |4-1| = 3
• |4-3| = 1
• |2-6| = 4
• |2-1| = 1
• |2-3| = 1
• |6-1| = 5
• |6-3| = 3
• |1-3| = 2

The minimum difference would be 1.

The key insight for solving this efficiently is recognizing that in a BST, an inorder traversal gives you nodes in sorted order. When values are sorted, the minimum difference must occur between adjacent values in that sorted sequence. This allows you to solve the problem in O(n) time by doing an inorder traversal and keeping track of the previous node's value, calculating differences only between consecutive nodes in the traversal.

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). A Binary Search Tree is indeed a graph 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). Trees are hierarchical data structures where each node has at most one parent and can have multiple children (in this case, at most two children for a binary tree).

DFS

• Conclusion: Based on the flowchart, when we have a tree structure, the algorithm leads us directly to DFS (Depth-First Search).

The flowchart suggests using DFS for this tree problem. This makes perfect sense because:

1. We need to visit all nodes in the tree to find all possible differences
2. DFS with inorder traversal on a BST gives us nodes in sorted order
3. The sorted order property allows us to optimize the solution by only comparing adjacent values in the traversal sequence

Therefore, the flowchart correctly identifies DFS as the appropriate pattern for solving the Minimum Absolute Difference in BST problem.

Intuition

The key insight comes from understanding the special property of Binary Search Trees. In a BST, for any node, all values in its left subtree are smaller, and all values in its right subtree are larger. This means when we perform an inorder traversal (left → root → right), we visit nodes in ascending order of their values.

Think about finding the minimum difference between any two numbers in a sorted array like [1, 3, 6, 10, 15]. You wouldn't compare 1 with 15, or 3 with 10. The minimum difference must occur between adjacent numbers because they are closest to each other on the number line. In this example, we'd check |3-1|=2, |6-3|=3, |10-6|=4, |15-10|=5, and find the minimum is 2.

The same logic applies to our BST problem. Instead of comparing every node with every other node (which would take O(n²) time), we can leverage the BST property. By doing an inorder DFS traversal, we get a sorted sequence of values. Then we only need to track the difference between consecutive values in this sequence.

During the traversal, we maintain a variable pre to remember the previous node's value. For each current node, we calculate current_value - pre (since values are in ascending order, current is always ≥ pre). We keep updating our answer with the minimum difference found so far. This way, we solve the problem in just one pass through the tree with O(n) time complexity.

The elegance of this solution lies in transforming a seemingly complex tree problem into a simple "find minimum difference in sorted sequence" problem by utilizing the inherent ordering property of BST traversal.

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

Solution Approach

The solution implements an inorder DFS traversal to visit all nodes in ascending order of their values. Let's walk through the implementation step by step:

1. Setting up the DFS function: We define a nested dfs function that takes the current node as input. This function will recursively traverse the tree in inorder fashion:

• First, visit the left subtree
• Then, process the current node
• Finally, visit the right subtree

2. Base case: If the current node is None, we simply return. This handles leaf nodes' null children and empty trees.

3. Inorder traversal pattern:

dfs(root.left)    # Visit left subtree first
# Process current node
dfs(root.right)   # Visit right subtree last

This order ensures we visit nodes from smallest to largest value.

4. Tracking the minimum difference: We use two variables declared with nonlocal scope:

• pre: Stores the value of the previously visited node in the inorder sequence
• ans: Stores the minimum difference found so far

For each node during traversal, we calculate root.val - pre. Since inorder traversal gives us values in ascending order, the current value is always greater than or equal to pre, so we don't need absolute value.

5. Initialization:

• pre = -inf: We initialize the previous value to negative infinity. This ensures the first node doesn't contribute to the answer (since node.val - (-inf) would be infinity)
• ans = inf: We initialize the answer to positive infinity so any valid difference will be smaller

6. Updating state: After calculating the difference with the previous node, we update pre = root.val so the current node becomes the "previous" node for the next iteration.

7. Final result: After the complete traversal, ans contains the minimum difference between any two adjacent nodes in the sorted sequence, which is guaranteed to be the minimum difference between any two nodes in the tree.

The algorithm runs in O(n) time where n is the number of nodes, as we visit each node exactly once. The space complexity is O(h) where h is the height of the tree, due to the recursive call stack.

Example Walkthrough

Let's trace through the algorithm with a small BST:

       4
      / \
     2   6
    / \
   1   3

Step-by-step execution:

1. Initialize: pre = -inf, ans = inf

2. Start DFS from root (4):

   • First, go left to node 2

3. At node 2:

   • First, go left to node 1

4. At node 1:

   • Go left: null, return
   • Process node 1:
     • Calculate: 1 - (-inf) = inf (don't update ans)
     • Update: pre = 1
   • Go right: null, return

5. Back at node 2:

   • Left subtree done
   • Process node 2:
     • Calculate: 2 - 1 = 1
     • Update: ans = min(inf, 1) = 1
     • Update: pre = 2
   • Go right to node 3

6. At node 3:

   • Go left: null, return
   • Process node 3:
     • Calculate: 3 - 2 = 1
     • Update: ans = min(1, 1) = 1
     • Update: pre = 3
   • Go right: null, return

7. Back at root (4):

   • Left subtree done
   • Process node 4:
     • Calculate: 4 - 3 = 1
     • Update: ans = min(1, 1) = 1
     • Update: pre = 4
   • Go right to node 6

8. At node 6:

   • Go left: null, return
   • Process node 6:
     • Calculate: 6 - 4 = 2
     • Update: ans = min(1, 2) = 1
     • Update: pre = 6
   • Go right: null, return

Result: The minimum difference is 1

The inorder traversal visited nodes in order: 1 → 2 → 3 → 4 → 6, and we only compared adjacent pairs: (1,2), (2,3), (3,4), (4,6), finding differences of 1, 1, 1, and 2 respectively.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes in the binary search tree.

The algorithm performs an in-order traversal of the binary search tree using depth-first search (DFS). During this traversal, each node is visited exactly once. At each node, the algorithm performs constant-time operations: comparing values to update the minimum difference (ans = min(ans, root.val - pre)) and updating the previous value (pre = root.val). Since we visit all n nodes exactly once and perform O(1) operations at each node, the overall time complexity is O(n).

Space Complexity: O(n) in the worst case, O(log n) in the best case for a balanced tree.

The space complexity is determined by the recursive call stack used during the DFS traversal. In the worst case, when the binary search tree is completely unbalanced (essentially a linked list), the recursion depth can reach n, resulting in O(n) space complexity. In the best case, when the tree is perfectly balanced, the maximum recursion depth is the height of the tree, which is O(log n). The auxiliary space used by the variables pre and ans is O(1), which doesn't affect the overall space complexity dominated by the recursion stack.

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

Common Pitfalls

1. Forgetting to handle the first node properly

A common mistake is not initializing the previous_value correctly, which can lead to incorrect calculations or runtime errors.

Pitfall Example:

def getMinimumDifference(self, root):
    def inorder(node):
        if not node:
            return
      
        inorder(node.left)
      
        nonlocal prev, min_diff
        # BUG: What if prev is None initially?
        min_diff = min(min_diff, abs(node.val - prev))
        prev = node.val
      
        inorder(node.right)
  
    prev = None  # Wrong initialization!
    min_diff = float('inf')
    inorder(root)
    return min_diff

Solution: Initialize previous_value to negative infinity (or use a flag to skip the first node):

# Option 1: Use -inf
previous_value = float('-inf')

# Option 2: Use a flag
first_node = True
if first_node:
    first_node = False
else:
    min_difference = min(min_difference, node.val - previous_value)

2. Using absolute value unnecessarily

Since inorder traversal of a BST gives values in ascending order, the current value is always ≥ previous value. Using abs() adds unnecessary computation.

Pitfall Example:

# Unnecessary use of abs()
min_difference = min(min_difference, abs(node.val - previous_value))

Solution: Simply use subtraction without absolute value:

min_difference = min(min_difference, node.val - previous_value)

3. Comparing all pairs instead of adjacent values

Some might try to store all values and compare every pair, leading to O(n²) time complexity.

Pitfall Example:

def getMinimumDifference(self, root):
    values = []
  
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        values.append(node.val)
        inorder(node.right)
  
    inorder(root)
    min_diff = float('inf')
  
    # O(n²) comparison - inefficient!
    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: Only compare adjacent values in the sorted sequence:

# O(n) comparison - efficient!
for i in range(1, len(values)):
    min_diff = min(min_diff, values[i] - values[i-1])

4. Not declaring variables as nonlocal

Forgetting to use the nonlocal keyword for variables modified inside the nested function causes UnboundLocalError.

Pitfall Example:

def getMinimumDifference(self, root):
    def inorder(node):
        if not node:
            return
      
        inorder(node.left)
      
        # ERROR: UnboundLocalError without nonlocal
        min_difference = min(min_difference, node.val - previous_value)
        previous_value = node.val
      
        inorder(node.right)
  
    previous_value = float('-inf')
    min_difference = float('inf')
    inorder(root)
    return min_difference

Solution: Declare variables as nonlocal before modifying them:

def inorder(node):
    if not node:
        return
  
    inorder(node.left)
  
    nonlocal previous_value, min_difference  # Declare as nonlocal
    min_difference = min(min_difference, node.val - previous_value)
    previous_value = node.val
  
    inorder(node.right)