Minimum Absolute Difference in BST

Problem Statement

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.

What to notice first

• In a BST, an in-order traversal yields values in ascending sorted order.
• The minimum difference must occur between consecutive values in sorted order.
• You do not need to compare all pairs; sorting the values is implicit via in-order traversal.

Examples

Input	Output	Explanation
Tree: 4, 2→1, 2→3, 6	1	Sorted values: [1, 2, 3, 4, 6]. Min diff = 2 - 1 = 1
Tree: 1, 0, 48→24, 48→null	24	Sorted values: [0, 1, 24, 48]. Min diff = 24 - 0 = 24

Constraints

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

Real-World Applications

Where this pattern appears

• Sensor calibration — given multiple sensor readings, find the two closest readings to identify if sensors are drifting.
• Stock price pairs — find the two stock prices with the smallest difference to identify arbitrage opportunities.
• Machine tolerance ranges — verify that all manufactured parts fall within acceptable variance.
• Binary classification thresholds — determine the optimal boundary between two classes by minimizing class difference.

Complexity Comparison

Approach	Time	Space	Key Idea	Best When
In-Order DFS	O(n)	O(h)	Visit nodes in sorted order; compare adjacent pairs only	General case — standard BST usage
BFS Level-Order	O(n log n)	O(w)	Collect all values, sort, then find min diff	Tree structure unknown or comparison required

Which approach should you learn first?

• Pick In-Order DFS if you want the most elegant and efficient solution.
• Pick BFS Level-Order if you prefer a simpler mental model (collect all, sort, compare).

Best For Speed

In-Order DFS

O(n) time · O(h) space

Simpler Mental Model

BFS Level-Order

O(n log n) time · O(w) space

Approach 1: In-Order DFS (Recommended)

★ Recommended

Traverse the BST in in-order (left → node → right), which visits nodes in ascending sorted order. As you visit each node, compare its value with the previously visited value. The minimum difference must occur between two consecutive values in this sorted sequence.

⏱ Time O(n) Single pass 💾 Space O(h) Recursion stack

Step-by-step Example

Input: Tree with values [4, 2, 6, 1, 3]

Step	Node	prev	Diff	min_diff	Action
1	1	null	—	∞	First node, store prev = 1
2	2	1	2 - 1 = 1	1	Update min_diff = 1
3	3	2	3 - 2 = 1	1	min_diff = 1
4	4	3	4 - 3 = 1	1	min_diff = 1
5	6	4	6 - 4 = 2	1	min_diff stays 1

Animated walkthrough

How in-order DFS finds the minimum difference

Watch the in-order traversal visit nodes in sorted order, comparing each node with its previous neighbor.

Back Autoplay Next Reset

Step 1 of 3 Target: 1

Waiting to begin...

Array state

Memory / lookup state

Pseudocode

function getMinimumDifference_inorder(root):
    min_diff = infinity
    prev = null

    function inorder(node):
        if node is null:
            return

        inorder(node.left)

        // Visit node
        if prev is not null:
            min_diff = min(min_diff, node.val - prev)
        prev = node.val

        inorder(node.right)

    inorder(root)
    return min_diff

Solution Code

Python

minimum_absolute_difference_in_bst_inorder.py

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def get_minimum_difference_inorder_dfs(root: Optional[TreeNode]) -> int:
    """
    In-order DFS approach to find minimum absolute difference in BST.

    In a BST, in-order traversal yields sorted values.
    We track the previous value and compute differences.

    Time: O(n) - visit each node once
    Space: O(h) - recursion stack, h = height
    """
    min_diff = [float('inf')]
    prev = [None]

    def inorder(node):
        if not node:
            return

        # Traverse left subtree
        inorder(node.left)

        # Process current node
        if prev[0] is not None:
            min_diff[0] = min(min_diff[0], node.val - prev[0])
        prev[0] = node.val

        # Traverse right subtree
        inorder(node.right)

    inorder(root)
    return min_diff[0]


# Test cases
if __name__ == "__main__":
    # Example 1: BST with multiple nodes
    root1 = TreeNode(4)
    root1.left = TreeNode(2)
    root1.right = TreeNode(6)
    root1.left.left = TreeNode(1)
    root1.left.right = TreeNode(3)
    print(get_minimum_difference_inorder_dfs(root1))  # 1

    # Example 2: Single path
    root2 = TreeNode(1)
    root2.right = TreeNode(5)
    root2.right.left = TreeNode(4)
    print(get_minimum_difference_inorder_dfs(root2))  # 1

C++

minimum_absolute_difference_in_bst_inorder.cpp

#include <iostream>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
private:
    int minDiff = INT_MAX;
    TreeNode* prev = nullptr;

    void inorder(TreeNode* node) {
        if (!node) return;

        // Traverse left subtree
        inorder(node->left);

        // Process current node
        if (prev != nullptr) {
            minDiff = min(minDiff, node->val - prev->val);
        }
        prev = node;

        // Traverse right subtree
        inorder(node->right);
    }

public:
    int getMinimumDifference(TreeNode* root) {
        inorder(root);
        return minDiff;
    }
};

int main() {
    // Example 1
    TreeNode* root1 = new TreeNode(4);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(6);
    root1->left->left = new TreeNode(1);
    root1->left->right = new TreeNode(3);

    Solution sol;
    cout << sol.getMinimumDifference(root1) << endl;  // 1

    return 0;
}

Java

MinimumAbsoluteDifferenceInBST_inorder.java

public class MinimumAbsoluteDifferenceInBST_InorderDFS {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    int minDiff = Integer.MAX_VALUE;
    TreeNode prev = null;

    private void inorder(TreeNode node) {
        if (node == null) return;

        // Traverse left subtree
        inorder(node.left);

        // Process current node
        if (prev != null) {
            minDiff = Math.min(minDiff, node.val - prev.val);
        }
        prev = node;

        // Traverse right subtree
        inorder(node.right);
    }

    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return minDiff;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(6);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);

        MinimumAbsoluteDifferenceInBST_InorderDFS sol = new MinimumAbsoluteDifferenceInBST_InorderDFS();
        System.out.println(sol.getMinimumDifference(root));  // 1
    }
}

JavaScript

minimum_absolute_difference_in_bst_inorder.js

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function getMinimumDifferenceInorderDFS(root) {
    let minDiff = Infinity;
    let prev = null;

    function inorder(node) {
        if (!node) return;

        // Traverse left subtree
        inorder(node.left);

        // Process current node
        if (prev !== null) {
            minDiff = Math.min(minDiff, node.val - prev);
        }
        prev = node.val;

        // Traverse right subtree
        inorder(node.right);
    }

    inorder(root);
    return minDiff;
}

// Test cases
const root1 = new TreeNode(4);
root1.left = new TreeNode(2);
root1.right = new TreeNode(6);
root1.left.left = new TreeNode(1);
root1.left.right = new TreeNode(3);
console.log(getMinimumDifferenceInorderDFS(root1));  // 1

const root2 = new TreeNode(1);
root2.right = new TreeNode(5);
root2.right.left = new TreeNode(4);
console.log(getMinimumDifferenceInorderDFS(root2));  // 1

Rust

minimum_absolute_difference_in_bst_inorder.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::min;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

pub fn get_minimum_difference_inorder_dfs(
    root: Option<Rc<RefCell<TreeNode>>>,
) -> i32 {
    let mut min_diff = i32::MAX;
    let mut prev: Option<i32> = None;

    fn inorder(
        node: &Option<Rc<RefCell<TreeNode>>>,
        min_diff: &mut i32,
        prev: &mut Option<i32>,
    ) {
        if let Some(n) = node {
            let n = n.borrow();

            // Traverse left subtree
            inorder(&n.left, min_diff, prev);

            // Process current node
            if let Some(p) = prev {
                *min_diff = min(*min_diff, n.val - p);
            }
            *prev = Some(n.val);

            // Traverse right subtree
            inorder(&n.right, min_diff, prev);
        }
    }

    inorder(&root, &mut min_diff, &mut prev);
    min_diff
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(4)));
    let left = Rc::new(RefCell::new(TreeNode::new(2)));
    let right = Rc::new(RefCell::new(TreeNode::new(6)));

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right.clone());

    let left_left = Rc::new(RefCell::new(TreeNode::new(1)));
    let left_right = Rc::new(RefCell::new(TreeNode::new(3)));

    left.borrow_mut().left = Some(left_left);
    left.borrow_mut().right = Some(left_right);

    println!("{}", get_minimum_difference_inorder_dfs(Some(root)));  // 1
}

Go

minimum_absolute_difference_in_bst_inorder.go

package main

import (
    "fmt"
    "math"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func GetMinimumDifferenceInorderDFS(root *TreeNode) int {
    minDiff := math.MaxInt32
    var prev *int

    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        // Traverse left subtree
        inorder(node.Left)

        // Process current node
        if prev != nil {
            diff := node.Val - *prev
            if diff < minDiff {
                minDiff = diff
            }
        }
        prev = &node.Val

        // Traverse right subtree
        inorder(node.Right)
    }

    inorder(root)
    return minDiff
}

func main() {
    root := &TreeNode{Val: 4}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 6}
    root.Left.Left = &TreeNode{Val: 1}
    root.Left.Right = &TreeNode{Val: 3}

    fmt.Println(GetMinimumDifferenceInorderDFS(root))  // 1
}

Approach 2: BFS Level-Order

🎯 Interview Favourite

Perform a level-order (breadth-first) traversal to collect all node values, sort them, then iterate through consecutive pairs to find the minimum difference.

This approach trades O(n log n) time for a simpler, more straightforward algorithm that does not rely on understanding BST properties.

⏱ Time O(n log n) Sorting overhead 💾 Space O(w) Queue + values

Step-by-step Example

Input: Tree with values [4, 2, 6, 1, 3]

1. BFS Traversal: Collect [4, 2, 6, 1, 3]
2. Sort: [1, 2, 3, 4, 6]
3. Find min diff between consecutive pairs:
   • 2 - 1 = 1
   • 3 - 2 = 1
   • 4 - 3 = 1
   • 6 - 4 = 2
   • Result: 1

Pseudocode

function getMinimumDifference_bfs(root):
    if root is null:
        return 0

    values = []
    queue = [root]

    // Collect all values via BFS
    while queue is not empty:
        node = queue.pop()
        values.append(node.val)
        if node.left:
            queue.push(node.left)
        if node.right:
            queue.push(node.right)

    // Sort values
    sort(values)

    // Find min diff between consecutive values
    min_diff = infinity
    for i in range(1, len(values)):
        min_diff = min(min_diff, values[i] - values[i-1])

    return min_diff

Solution Code

Python

minimum_absolute_difference_in_bst_bfs.py

from typing import Optional


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def get_minimum_difference_bfs(root: Optional[TreeNode]) -> int:
    """
    BFS level-order traversal to find minimum absolute difference in BST.

    Perform in-order traversal using an iterative approach with a stack,
    then compute minimum difference between consecutive values.

    Time: O(n) - visit each node once
    Space: O(h) - queue/stack space, h = height
    """
    if not root:
        return 0

    # Iterative in-order using stack
    stack = []
    current = root
    prev = None
    min_diff = float('inf')

    while stack or current:
        # Go to leftmost node
        while current:
            stack.append(current)
            current = current.left

        # Current is None, pop from stack
        current = stack.pop()

        # Process current node
        if prev is not None:
            min_diff = min(min_diff, current.val - prev)
        prev = current.val

        # Visit right subtree
        current = current.right

    return min_diff


# Test cases
if __name__ == "__main__":
    # Example 1: BST with multiple nodes
    root1 = TreeNode(4)
    root1.left = TreeNode(2)
    root1.right = TreeNode(6)
    root1.left.left = TreeNode(1)
    root1.left.right = TreeNode(3)
    print(get_minimum_difference_bfs(root1))  # 1

    # Example 2: Single path
    root2 = TreeNode(1)
    root2.right = TreeNode(5)
    root2.right.left = TreeNode(4)
    print(get_minimum_difference_bfs(root2))  # 1

C++

minimum_absolute_difference_in_bst_bfs.cpp

#include <iostream>
#include <stack>
#include <climits>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int getMinimumDifference(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* current = root;
        TreeNode* prev = nullptr;
        int minDiff = INT_MAX;

        while (!st.empty() || current) {
            // Go to leftmost node
            while (current) {
                st.push(current);
                current = current->left;
            }

            // Current is null, pop from stack
            current = st.top();
            st.pop();

            // Process current node
            if (prev != nullptr) {
                minDiff = min(minDiff, current->val - prev->val);
            }
            prev = current;

            // Visit right subtree
            current = current->right;
        }

        return minDiff;
    }
};

int main() {
    TreeNode* root1 = new TreeNode(4);
    root1->left = new TreeNode(2);
    root1->right = new TreeNode(6);
    root1->left->left = new TreeNode(1);
    root1->left->right = new TreeNode(3);

    Solution sol;
    cout << sol.getMinimumDifference(root1) << endl;  // 1

    return 0;
}

Java

MinimumAbsoluteDifferenceInBST_bfs.java

import java.util.*;

class Solution {
    public int getMinimumDifference(TreeNode root) {
        int minDiff = Integer.MAX_VALUE;
        Integer prevVal = null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) continue;

            if (prevVal != null) {
                minDiff = Math.min(minDiff, Math.abs(node.val - prevVal));
            }
            prevVal = node.val;

            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }

        return minDiff;
    }
}

System.out.println("MinDiff Solution");

JavaScript

minimum_absolute_difference_in_bst_bfs.js

class TreeNode {
    constructor(val = 0, left = null, right = null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

function getMinimumDifferenceBFS(root) {
    const stack = [];
    let current = root;
    let prev = null;
    let minDiff = Infinity;

    while (stack.length > 0 || current) {
        // Go to leftmost node
        while (current) {
            stack.push(current);
            current = current.left;
        }

        // Current is null, pop from stack
        current = stack.pop();

        // Process current node
        if (prev !== null) {
            minDiff = Math.min(minDiff, current.val - prev);
        }
        prev = current.val;

        // Visit right subtree
        current = current.right;
    }

    return minDiff;
}

// Test cases
const root1 = new TreeNode(4);
root1.left = new TreeNode(2);
root1.right = new TreeNode(6);
root1.left.left = new TreeNode(1);
root1.left.right = new TreeNode(3);
console.log(getMinimumDifferenceBFS(root1));  // 1

const root2 = new TreeNode(1);
root2.right = new TreeNode(5);
root2.right.left = new TreeNode(4);
console.log(getMinimumDifferenceBFS(root2));  // 1

Rust

minimum_absolute_difference_in_bst_bfs.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::cmp::min;

#[derive(Debug)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}

pub fn get_minimum_difference_bfs(
    root: Option<Rc<RefCell<TreeNode>>>,
) -> i32 {
    if root.is_none() {
        return 0;
    }

    let mut stack = Vec::new();
    let mut current = root;
    let mut prev: Option<i32> = None;
    let mut min_diff = i32::MAX;

    loop {
        // Go to leftmost node
        while let Some(node) = current {
            stack.push(node.clone());
            current = node.borrow_mut().left.take();
        }

        if stack.is_empty() {
            break;
        }

        // Pop from stack
        let node = stack.pop().unwrap();
        let node_ref = node.borrow();

        // Process current node
        if let Some(p) = prev {
            min_diff = min(min_diff, node_ref.val - p);
        }
        prev = Some(node_ref.val);

        // Visit right subtree
        current = node_ref.right.as_ref().cloned();
    }

    min_diff
}

fn main() {
    let root = Rc::new(RefCell::new(TreeNode::new(4)));
    let left = Rc::new(RefCell::new(TreeNode::new(2)));
    let right = Rc::new(RefCell::new(TreeNode::new(6)));

    root.borrow_mut().left = Some(left.clone());
    root.borrow_mut().right = Some(right.clone());

    let left_left = Rc::new(RefCell::new(TreeNode::new(1)));
    let left_right = Rc::new(RefCell::new(TreeNode::new(3)));

    left.borrow_mut().left = Some(left_left);
    left.borrow_mut().right = Some(left_right);

    println!("{}", get_minimum_difference_bfs(Some(root)));  // 1
}

Go

minimum_absolute_difference_in_bst_bfs.go

package main

import (
    "fmt"
    "math"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func GetMinimumDifferenceBFS(root *TreeNode) int {
    if root == nil {
        return 0
    }

    var stack []*TreeNode
    current := root
    var prev *int
    minDiff := math.MaxInt32

    for len(stack) > 0 || current != nil {
        // Go to leftmost node
        for current != nil {
            stack = append(stack, current)
            current = current.Left
        }

        // Pop from stack
        if len(stack) == 0 {
            break
        }
        current = stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        // Process current node
        if prev != nil {
            diff := current.Val - *prev
            if diff < minDiff {
                minDiff = diff
            }
        }
        prev = &current.Val

        // Visit right subtree
        current = current.Right
    }

    return minDiff
}

func main() {
    root := &TreeNode{Val: 4}
    root.Left = &TreeNode{Val: 2}
    root.Right = &TreeNode{Val: 6}
    root.Left.Left = &TreeNode{Val: 1}
    root.Left.Right = &TreeNode{Val: 3}

    fmt.Println(GetMinimumDifferenceBFS(root))  // 1
}

Common mistakes

Watch for these pitfalls

• Comparing all pairs: Forgetting that minimum diff must occur between consecutive sorted values. O(n²) comparisons are unnecessary.
• Ignoring BST property: The BST property guarantees in-order traversal is sorted. Use it!
• Off-by-one errors: When iterating through sorted values, ensure you compare values[i] - values[i-1] for all i ≥ 1.
• Not handling single-node trees: Although constraints say n ≥ 2, defensive checks are safe.

Related Problems

• Validate Binary Search Tree ↗ Medium #98
• Lowest Common Ancestor of a Binary Search Tree ↗ Easy #235
• Kth Smallest Element in a BST ↗ Medium #230
• Binary Tree Inorder Traversal ↗ Easy #94

Interview Tips

Key trade-offs to discuss

• In-Order DFS vs BFS: In-order naturally maintains sorted order, eliminating the need for explicit sorting. This is the signature BST property and the interviewer likely wants to see you leverage it.
• Space complexity: In-Order uses O(h) recursion stack (often optimal for balanced trees). BFS uses O(w) for the queue, which can be O(n) for skewed trees or wide trees.
• Edge cases: Empty tree (handled by constraints), single edge difference, duplicate values (problem states all unique).
• Follow-up: “Can you do this iteratively?” Yes — use an explicit stack to simulate the recursion for in-order traversal.

← Previous
#529 Binary Tree Maximum Path Sum Next
#531 Lonely Pixel I →