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 — DFS

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

Preview

Recognizing the BST property allows the problem to be reduced to finding the minimum difference between consecutive values in a sorted list…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

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…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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

Python

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

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

3

Invoke DFS and Return the Computed Minimum Difference

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

2 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

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`