Minimum Absolute Difference in BST - Practice Coding Problems

Minimum Absolute Difference in BST - 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.

A BST is a binary tree where for every node:

All values in the left subtree are less than the node's value
All values in the right subtree are greater than the node's value

The absolute difference between two values a and b is |a - b|.

Input & Output

Example 1 — Basic BST

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

› Output: 1

💡 Note: The tree has values 4,2,6,1,3. Inorder traversal gives [1,2,3,4,6]. Adjacent differences are: 2-1=1, 3-2=1, 4-3=1, 6-4=2. Minimum is 1.

Example 2 — Small BST

$ Input: root = [1,0,48,null,null,12,49]

› Output: 1

💡 Note: The tree has values 1,0,48,12,49. Inorder gives [0,1,12,48,49]. Adjacent differences: 1-0=1, 12-1=11, 48-12=36, 49-48=1. Minimum is 1.

Example 3 — Two Nodes

$ Input: root = [1,null,3]

› Output: 2

💡 Note: Only two nodes with values 1 and 3. The absolute difference is |3-1| = 2.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary Search Tree with values [4,2,6,1,3]

Inorder Traversal

BST inorder gives sorted sequence: 1→2→3→4→6

Adjacent Differences

Minimum difference is between consecutive values: min(1,1,1,2) = 1

Key Takeaway

🎯 Key Insight: BST inorder traversal gives sorted values, so minimum difference is always between adjacent elements

Asked in

G Google 15 a Amazon 12 M Microsoft 8 🍎 Apple 6

The key insight is that BST inorder traversal produces sorted values. Instead of comparing all pairs, we only need to check adjacent elements in the sorted sequence. Best approach is inorder DFS with single pass comparison. Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Inorder Traversal	O(n)	O(h)	Use BST property: inorder traversal gives sorted sequence, compare adjacent elements
Sort Values Then Compare Adjacent	O(n log n)	O(n)	Collect all values, sort them, then find minimum difference between adjacent elements
Brute Force - Compare All Pairs	O(n²)	O(n)	Extract all values and compare every pair to find minimum difference

DFS with Inorder Traversal — Algorithm Steps

Step 1: Perform inorder DFS traversal of BST
Step 2: Track previous node value during traversal
Step 3: Calculate difference with previous value and update minimum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int minDiff;
int prev;
int hasPrev;

void inorder(struct TreeNode* node) {
    if (!node) return;
    
    inorder(node->left);
    
    if (hasPrev) {
        int diff = abs(node->val - prev);
        if (diff < minDiff) minDiff = diff;
    }
    prev = node->val;
    hasPrev = 1;
    
    inorder(node->right);
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    minDiff = INT_MAX;
    hasPrev = 0;
    inorder(root);
    return minDiff;
}

int main() {
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(6);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    
    printf("%d\n", solution(root));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal visits each node exactly once

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h

✓ Linear Space

189.0K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen