Minimum Absolute Difference in BST

Easy
1872.

Minimum Absolute Difference in BST

Minimum Absolute Difference in BST is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Given the root of a binary search tree with distinct values, return the minimum absolute difference between the values of any two different nodes.

Example 1

Input
root = [4,2,6,1,3]
Output
1
Explanation
Several pairs differ by 1, for example 1 and 2, or 3 and 4.

Example 2

Input
root = [1,0,48,null,null,12,49]
Output
1
Explanation
Inorder the values are 0, 1, 12, 48, 49; both 0 and 1 and 48 and 49 differ by 1.

Example 3

Input
root = [10,null,100000]
Output
99990

Constraints

  • The number of nodes in the tree is in the range [2, 10^4]
  • 0 <= Node.val <= 10^5
  • All values are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Absolute Difference in BST — Problem & Solution

Minimum Absolute Difference in BST solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Minimum Absolute Difference in BST is an easy coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

Given the root of a binary search tree with distinct values, return the minimum absolute difference between the values of any two different nodes.

Example 1

Input: root = [4,2,6,1,3]
Output: 1
Explanation: Several pairs differ by 1, for example 1 and 2, or 3 and 4.

Example 2

Input: root = [1,0,48,null,null,12,49]
Output: 1
Explanation: Inorder the values are 0, 1, 12, 48, 49; both 0 and 1 and 48 and 49 differ by 1.

Example 3

Input: root = [10,null,100000]
Output: 99990

Constraints

  • The number of nodes in the tree is in the range [2, 10^4]
  • 0 <= Node.val <= 10^5
  • All values are distinct

Hints for Minimum Absolute Difference in BST

  1. Hint 1

    In sorted order, the closest pair of numbers is always a pair of neighbours.

  2. Hint 2

    An inorder walk of a BST lists its values in sorted order.

  3. Hint 3

    So walk inorder, remembering only the previous value, and take the smallest gap between consecutive values.

How to solve Minimum Absolute Difference in BST

Sorted order puts the closest two values next to each other, and inorder traversal of a BST is sorted order. One inorder pass comparing each value with the one before it finds the answer.

Approach

  1. Walk the BST inorder, keeping the previously visited value (none at the start).
  2. At each node, if there is a previous value, update best = min(best, val - prev).
  3. Set prev = val and continue.
  4. Return best.

Why it works

For sorted values a1 < a2 < … < an, any pair ai < aj with a gap of more than one position has aj - ai >= a(i+1) - ai, so some adjacent pair is at least as close. Inorder visits exactly the sorted sequence, so its consecutive differences include the minimum.

Complexity

  • Time — O(n)
  • Space — O(h) for the traversal

Pitfalls

  • Comparing only parents with children is not enough: in the first example 3 and 4 differ by 1, yet 3 is a grandchild of 4.
  • Values start at 0, so do not use 0 as a 'no previous value' marker.

Reference solution

Python

from typing import Optional

def getMinimumDifference(root: Optional[TreeNode]) -> int:
    best = float("inf")
    prev = None
    stack = []
    cur = root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        if prev is not None:
            best = min(best, cur.val - prev)
        prev = cur.val
        cur = cur.right
    return int(best)

Java

public static int getMinimumDifference(TreeNode root) {
    int best = Integer.MAX_VALUE, prev = -1;
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (prev >= 0) best = Math.min(best, cur.val - prev);
        prev = cur.val;
        cur = cur.right;
    }
    return best;
}

C++

int getMinimumDifference(TreeNode* root) {
    int best = INT_MAX, prev = -1;
    vector<TreeNode*> stack;
    TreeNode* cur = root;
    while (cur || !stack.empty()) {
        while (cur) {
            stack.push_back(cur);
            cur = cur->left;
        }
        cur = stack.back();
        stack.pop_back();
        if (prev >= 0) best = min(best, cur->val - prev);
        prev = cur->val;
        cur = cur->right;
    }
    return best;
}

JavaScript

var getMinimumDifference = function(root) {
    var best = Infinity, prev = null;
    var stack = [], cur = root;
    while (cur !== null || stack.length > 0) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        if (prev !== null) best = Math.min(best, cur.val - prev);
        prev = cur.val;
        cur = cur.right;
    }
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)