What pattern does Minimum Absolute Difference in BST use?

The Pattern: DFS (Inorder Traversal on BST) The Heuristic: In BST problems requiring sorted order or minimum differences, an inorder DFS traversal reveals the sorted sequence, enabling efficient computation by comparing only adjacent nodes without extra storage.

Minimum Absolute Difference in BST

Q: What is the time complexity of Minimum Absolute Difference in BST?

O(n). Each node is visited exactly once during the inorder traversal, resulting in linear time complexity proportional to the number of nodes.

Problem

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

The number of nodes in the tree is in the range [2, 10⁴]
0 ≤ Node.val ≤ 10⁵

Example

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

Output: 1

A brute-force approach would compare every pair of nodes, resulting in O(n^2) time complexity. Instead, an inorder traversal of the BST visits nodes in ascending order, so the minimum difference must be between two consecutive nodes in this order. The algorithm performs an inorder DFS, tracking the previous node's value and updating the minimum difference whenever a smaller gap is found. For example, visiting nodes in order: 1, 2, 3, 4, 6, the minimum difference is min(2-1, 3-2, 4-3, 6-4) = 1.

Approach

Straightforward Solution

A brute-force approach compares every pair of nodes, resulting in O(n^2) time complexity, which is inefficient for large trees.

Core Observation

In a BST, an inorder traversal visits nodes in sorted ascending order. Therefore, the minimum absolute difference between any two nodes must be found between two adjacent nodes in this traversal.

Path to Optimal

Recognizing the BST property allows the problem to be reduced to finding the minimum difference between consecutive values in a sorted list. Instead of storing all values, the algorithm tracks only the previous node's value during inorder traversal, updating the minimum difference on the fly. This reduces space complexity and improves efficiency.

Optimal Approach

Perform an inorder DFS traversal of the BST, maintaining a variable to store the previous node's value and another for the minimum difference found so far. At each node, compute the difference with the previous value and update the minimum difference if smaller. Return the minimum difference after traversal completes.

Time

O(n)

Each node is visited exactly once during the inorder traversal, resulting in linear time complexity proportional to the number of nodes.

Space

O(h)

The auxiliary space is determined by the recursion stack, which is proportional to the height h of the BST. In the worst case (skewed tree), h can be O(n), but for balanced trees, h is O(log n). No additional data structures proportional to n are used.

Solution

1class Solution:
  def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
      self.prev = None
      self.min_diff = float("inf")
5
      def dfs(node):
          if not node:
              return
          
          dfs(node.left)
11
          if self.prev is not None:
              self.min_diff = min(self.min_diff, node.val - self.prev)
          self.prev = node.val
15
          dfs(node.right)
      
      dfs(root)
      return self.min_diff

Step-by-Step Solution

1

Initialize State Variables for Tracking Previous Node and Minimum Difference

3self.prev = None
4self.min_diff = float("inf")

Objective

To set up variables that hold the previous node's value and the minimum difference found so far during traversal.

Key Insight

Tracking only the previous node's value during inorder traversal avoids storing the entire sorted list of node values, optimizing space. Initializing the minimum difference to infinity ensures any valid difference found will update it.

Interview Quick-Check

Core Logic

Using a single variable to track the previous node's value enables constant space comparison between consecutive nodes.

State & Boundaries

Initializing previous value as None handles the first node case where no comparison is possible.

2

Perform Recursive Inorder DFS Traversal to Update Minimum Difference

6def dfs(node):
  if not node:
      return
  dfs(node.left)
  if self.prev is not None:
      self.min_diff = min(self.min_diff, node.val - self.prev)
  self.prev = node.val
  dfs(node.right)

Objective

To recursively traverse the BST inorder and update the minimum difference by comparing current node value with the previous node's value.

Key Insight

Inorder traversal visits nodes in ascending order, so the difference between the current node and the previous node is the smallest possible difference involving the current node. Updating the minimum difference at each step ensures the global minimum is found without extra storage.

Interview Quick-Check

Core Logic

The recursive inorder traversal visits left subtree, processes current node by updating min difference, then visits right subtree, ensuring sorted order.

State & Boundaries

The base case returns immediately on null nodes, preventing unnecessary recursion.

Common Pitfalls & Bugs

Forgetting to update the previous node's value after processing the current node leads to incorrect comparisons.

3

Invoke DFS and Return the Computed Minimum Difference

18dfs(root)
19return self.min_diff

Objective

To start the inorder traversal from the root and return the final minimum difference after traversal completes.

Key Insight

Starting the DFS from the root ensures the entire BST is traversed. Returning the stored minimum difference variable provides the final answer computed during traversal.

Interview Quick-Check

Core Logic

Calling dfs(root) initiates the traversal that computes the minimum difference.

State & Boundaries

Returning self.min_diff after traversal completes provides the correct final result.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 13 Critical

self.min_diff = min(self.min_diff, node.val - self.prev)

Update the minimum difference with the smaller of current and new difference.

This line is the core logic that maintains the global minimum difference by comparing consecutive node values in sorted order.

Line 14 Critical

self.prev = node.val

Update the previous node value to the current node's value.

Updating previous ensures the next node's difference is computed against the correct predecessor, maintaining the sorted sequence comparison.

Line 4 Core

self.min_diff = float("inf")

Initialize the minimum difference to positive infinity.

Starting with infinity guarantees that any valid difference found during traversal will update this value to a meaningful minimum.

Line 10 Core

dfs(node.left)

Recursively traverse the left subtree.

Inorder traversal requires visiting the left subtree before processing the current node to maintain ascending order.

Line 12 Core

if self.prev is not None:

Check if a previous node value exists to compute difference.

Skipping the difference calculation on the first node prevents invalid comparisons and errors.

Line 16 Core

dfs(node.right)

Recursively traverse the right subtree.

Inorder traversal visits the right subtree after processing the current node to maintain ascending order.

Line 19 Core

return self.min_diff

Return the minimum absolute difference found.

Returning the stored minimum difference after traversal completes provides the final answer to the problem.

Line 3 Core

self.prev = None

Initialize the previous node value tracker to None.

Setting previous to None handles the initial state before any nodes are visited, ensuring the first comparison is skipped safely.

Line 7 Core

if not node:

Check if the current node is None and return if so.

This base case prevents further recursion on empty branches, ensuring termination and correctness.

Line 18 Core

dfs(root)

Start the inorder DFS traversal from the root node.

This call initiates the entire traversal process that computes the minimum difference across the BST.

Line 6 Standard

def dfs(node):

Define the recursive DFS helper function for inorder traversal.

Encapsulating the traversal logic in a helper function allows clean recursion and state access via the outer scope.

Line 8 Standard

return

Return immediately if node is None (base case).

This explicit return stops recursion at leaf boundaries, avoiding errors and unnecessary calls.

Test Your Understanding

Why does comparing only consecutive nodes in an inorder traversal suffice to find the minimum absolute difference in a BST?

Because an inorder traversal of a BST visits nodes in ascending order, the smallest difference between any two nodes must be between two adjacent nodes in this sorted sequence. Differences between non-adjacent nodes are always larger or equal to some adjacent pair difference.

Don't just read it. Drill it.

Reconstruct Minimum Absolute Difference in BST from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Minimum Absolute Difference in BST drill

or drill a free problem

1	`class Solution:`
2	`def getMinimumDifference(self, root: Optional[TreeNode]) -> int:`
3	`self.prev = None`
4	`self.min_diff = float("inf")`
5
6	`def dfs(node):`
7	`if not node:`
8	`return`
9
10	`dfs(node.left)`
11
12	`if self.prev is not None:`
13	`self.min_diff = min(self.min_diff, node.val - self.prev)`
14	`self.prev = node.val`
15
16	`dfs(node.right)`
17
18	`dfs(root)`
19	`return self.min_diff`

6	`def dfs(node):`
7	`if not node:`
8	`return`
10	`dfs(node.left)`
12	`if self.prev is not None:`
13	`self.min_diff = min(self.min_diff, node.val - self.prev)`
14	`self.prev = node.val`
16	`dfs(node.right)`

Problem

Example

Approach

Solution

Step-by-Step Solution

Initialize State Variables for Tracking Previous Node and Minimum Difference

Perform Recursive Inorder DFS Traversal to Update Minimum Difference

Invoke DFS and Return the Computed Minimum Difference

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.