Minimum Distance Between BST Nodes - Practice Coding Problems

Minimum Distance Between BST Nodes - Problem

Given the root of a Binary Search Tree (BST), return the minimum 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

Note: The minimum difference is always positive since we're looking at different nodes.

Input & Output

Example 1 — Basic BST

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

› Output: 1

💡 Note: Inorder traversal gives [1,2,3,4,6]. Adjacent differences: |2-1|=1, |3-2|=1, |4-3|=1, |6-4|=2. Minimum is 1.

Example 2 — Larger Gaps

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

› Output: 1

💡 Note: Inorder traversal 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 — Small Tree

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

› Output: 2

💡 Note: Inorder traversal gives [1,3]. Only one difference: |3-1|=2.

Constraints

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

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

Find Minimum

Minimum consecutive difference is 1

Key Takeaway

🎯 Key Insight: BST inorder traversal automatically gives sorted values, making it easy to find minimum consecutive differences

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is leveraging BST's inorder traversal property - it naturally gives us values in sorted order. We can find the minimum difference by comparing consecutive nodes during a single inorder traversal. Best approach is Inorder DFS with Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Compare All Pairs	O(n²)	O(n)	Compare every node with every other node to find minimum difference
Inorder Traversal (Optimal)	O(n)	O(h)	Use inorder traversal to get sorted values, then find minimum consecutive difference

Brute Force - Compare All Pairs — Algorithm Steps

Step 1: Traverse tree to collect all node values
Step 2: Compare every pair of values
Step 3: Return the minimum difference found

Visualization

Tap to expand

Step-by-Step Walkthrough

Collect Values

Traverse tree to get all node values [1,2,3,4,6]

Compare Pairs

Check all possible 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

Find Minimum

Minimum difference found is 1

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 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void collectValues(struct TreeNode* node, int* values, int* count) {
    if (node) {
        values[(*count)++] = node->val;
        collectValues(node->left, values, count);
        collectValues(node->right, values, count);
    }
}

int abs_diff(int a, int b) {
    return a > b ? a - b : b - a;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    int values[1000];
    int count = 0;
    collectValues(root, values, &count);
    
    int minDiff = INT_MAX;
    for (int i = 0; i < count; i++) {
        for (int j = i + 1; j < count; j++) {
            int diff = abs_diff(values[i], values[j]);
            if (diff < minDiff) {
                minDiff = diff;
            }
        }
    }
    
    return minDiff;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Nested loops to compare all n×n pairs of nodes

⚠ Quadratic Growth

Space Complexity

O(n)

Store all n node values in a list

⚡ Linearithmic Space

71.8K Views

Medium Frequency

~15 min Avg. Time

1.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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Compare All Pairs — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler