783. Minimum Distance between BST Nodes - Explanation

Description

Return the smallest absolute difference between the values of two different nodes in the binary search tree. This is a difference between node values, not the number of edges between nodes.

The tree follows the binary search tree rule: every value in a node's left subtree is smaller than its value, and every value in its right subtree is larger.

Examples use level-order arrays. After the root, each present node contributes left and right child entries in queue order. null marks a missing child, and trailing missing entries may be omitted.

Example 1:

Minimum Distance Between BST Nodes, example 1: illustration of the example

Input: root = [10,4,20,1,7,15,30]

Output: 3

Explanation: The sorted values are [1,4,7,10,15,20,30]. The smallest gap is 3, achieved by several pairs, including 1 and 4.

Example 2:

Minimum Distance Between BST Nodes, example 2: illustration of the example

Input: root = [20,5,40,null,18]

Output: 2

Explanation: The values 18 and 20 differ by 2. No other pair is closer; these nodes need not be directly connected by an edge.

Example 3:

Minimum Distance Between BST Nodes, example 3: illustration of the example

Input: root = [0,null,100000]

Output: 100000

Explanation: There are only two nodes, with values 0 and 100000. Their absolute difference is 100000.

Constraints:

The tree contains between 2 and 100 nodes.
0 <= Node.val <= 100000
The input is a binary search tree with distinct node values.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Binary Search Tree (BST) Properties - Understanding that in a BST, left subtree values are smaller and right subtree values are larger than the root
Tree Traversal (DFS) - Ability to traverse binary trees using depth-first search, particularly inorder traversal
Inorder Traversal - Knowing that inorder traversal of a BST produces values in sorted (ascending) order

1. Brute Force (DFS)

Intuition

The most straightforward approach is to compare every pair of nodes in the tree. For each node, we traverse the entire tree to find the minimum absolute difference between this node's value and any other node's value. While simple to understand, this approach doesn't leverage the BST property and results in redundant comparisons.

Algorithm

Define a helper function dfs(node) that returns the minimum difference involving any node in the subtree rooted at node.
For each node visited, call another helper dfs1(root, node) that traverses the entire tree and computes the minimum difference between node and every other node.
Recursively compute the minimum for left and right subtrees.
Return the overall minimum difference found.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        def dfs(node):
            if not node:
                return float("inf")
            res = dfs1(root, node)
            res = min(res, dfs(node.left))
            res = min(res, dfs(node.right))
            return res

        def dfs1(root, node):
            if not root:
                return float("inf")

            res = float("inf")
            if root != node:
                res = abs(root.val - node.val)
            res = min(res, dfs1(root.left, node))
            res = min(res, dfs1(root.right, node))
            return res

        return dfs(root)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int minDiffInBST(TreeNode root) {
        return dfs(root, root);
    }

    private int dfs(TreeNode root, TreeNode node) {
        if (node == null) {
            return Integer.MAX_VALUE;
        }
        int res = dfs1(root, node);
        res = Math.min(res, dfs(root, node.left));
        res = Math.min(res, dfs(root, node.right));
        return res;
    }

    private int dfs1(TreeNode root, TreeNode node) {
        if (root == null) {
            return Integer.MAX_VALUE;
        }
        int res = Integer.MAX_VALUE;
        if (root != node) {
            res = Math.abs(root.val - node.val);
        }
        res = Math.min(res, dfs1(root.left, node));
        res = Math.min(res, dfs1(root.right, node));
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        return dfs(root, root);
    }

private:
    int dfs(TreeNode* root, TreeNode* node) {
        if (!node) {
            return INT_MAX;
        }
        int res = dfs1(root, node);
        res = min(res, dfs(root, node->left));
        res = min(res, dfs(root, node->right));
        return res;
    }

    int dfs1(TreeNode* root, TreeNode* node) {
        if (!root) {
            return INT_MAX;
        }
        int res = INT_MAX;
        if (root != node) {
            res = abs(root->val - node->val);
        }
        res = min(res, dfs1(root->left, node));
        res = min(res, dfs1(root->right, node));
        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    minDiffInBST(root) {
        const dfs = (node) => {
            if (!node) {
                return Infinity;
            }
            let res = dfs1(root, node);
            res = Math.min(res, dfs(node.left));
            res = Math.min(res, dfs(node.right));
            return res;
        };

        const dfs1 = (root, node) => {
            if (!root) {
                return Infinity;
            }
            let res = Infinity;
            if (root !== node) {
                res = Math.abs(root.val - node.val);
            }
            res = Math.min(res, dfs1(root.left, node));
            res = Math.min(res, dfs1(root.right, node));
            return res;
        };

        return dfs(root);
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MinDiffInBST(TreeNode root) {
        return Dfs(root, root);
    }

    private int Dfs(TreeNode root, TreeNode node) {
        if (node == null) return int.MaxValue;
        int res = Dfs1(root, node);
        res = Math.Min(res, Dfs(root, node.left));
        res = Math.Min(res, Dfs(root, node.right));
        return res;
    }

    private int Dfs1(TreeNode root, TreeNode node) {
        if (root == null) return int.MaxValue;
        int res = int.MaxValue;
        if (root != node) {
            res = Math.Abs(root.val - node.val);
        }
        res = Math.Min(res, Dfs1(root.left, node));
        res = Math.Min(res, Dfs1(root.right, node));
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDiffInBST(root *TreeNode) int {
    var dfs func(node *TreeNode) int
    var dfs1 func(r, node *TreeNode) int

    dfs1 = func(r, node *TreeNode) int {
        if r == nil {
            return math.MaxInt32
        }
        res := math.MaxInt32
        if r != node {
            res = abs(r.Val - node.Val)
        }
        res = min(res, dfs1(r.Left, node))
        res = min(res, dfs1(r.Right, node))
        return res
    }

    dfs = func(node *TreeNode) int {
        if node == nil {
            return math.MaxInt32
        }
        res := dfs1(root, node)
        res = min(res, dfs(node.Left))
        res = min(res, dfs(node.Right))
        return res
    }

    return dfs(root)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun minDiffInBST(root: TreeNode?): Int {
        return dfs(root, root)
    }

    private fun dfs(root: TreeNode?, node: TreeNode?): Int {
        if (node == null) return Int.MAX_VALUE
        var res = dfs1(root, node)
        res = minOf(res, dfs(root, node.left))
        res = minOf(res, dfs(root, node.right))
        return res
    }

    private fun dfs1(root: TreeNode?, node: TreeNode?): Int {
        if (root == null) return Int.MAX_VALUE
        var res = Int.MAX_VALUE
        if (root !== node) {
            res = kotlin.math.abs(root.`val` - node!!.`val`)
        }
        res = minOf(res, dfs1(root.left, node))
        res = minOf(res, dfs1(root.right, node))
        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func minDiffInBST(_ root: TreeNode?) -> Int {
        return dfs(root, root)
    }

    private func dfs(_ root: TreeNode?, _ node: TreeNode?) -> Int {
        guard let node = node else { return Int.max }
        var res = dfs1(root, node)
        res = min(res, dfs(root, node.left))
        res = min(res, dfs(root, node.right))
        return res
    }

    private func dfs1(_ root: TreeNode?, _ node: TreeNode) -> Int {
        guard let root = root else { return Int.max }
        var res = Int.max
        if root !== node {
            res = abs(root.val - node.val)
        }
        res = min(res, dfs1(root.left, node))
        res = min(res, dfs1(root.right, node))
        return res
    }
}

use std::ptr;

impl Solution {
    pub fn min_diff_in_bst(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::dfs(&root, &root)
    }

    fn dfs(
        root: &Option<Rc<RefCell<TreeNode>>>,
        node: &Option<Rc<RefCell<TreeNode>>>,
    ) -> i32 {
        match node {
            None => i32::MAX,
            Some(n) => {
                let nb = n.borrow();
                let mut res = Self::dfs1(root, node);
                res = res.min(Self::dfs(root, &nb.left));
                res = res.min(Self::dfs(root, &nb.right));
                res
            }
        }
    }

    fn dfs1(
        root: &Option<Rc<RefCell<TreeNode>>>,
        node: &Option<Rc<RefCell<TreeNode>>>,
    ) -> i32 {
        match root {
            None => i32::MAX,
            Some(r) => {
                let rb = r.borrow();
                let node_rc = node.as_ref().unwrap();
                let same = ptr::eq(
                    r.as_ptr() as *const (),
                    node_rc.as_ptr() as *const (),
                );
                let mut res = if !same {
                    (rb.val - node_rc.borrow().val).abs()
                } else {
                    i32::MAX
                };
                res = res.min(Self::dfs1(&rb.left, node));
                res = res.min(Self::dfs1(&rb.right, node));
                res
            }
        }
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Inorder Traversal

Intuition

In a BST, an inorder traversal visits nodes in sorted order. The minimum difference between any two nodes must occur between consecutive elements in this sorted sequence. So we perform an inorder traversal to collect all values into an array, then scan through the array to find the minimum difference between adjacent elements.

Algorithm

Perform an inorder traversal (left, root, right) and collect all node values into an array.
The array is now sorted in ascending order.
Iterate through the array and compute the difference between each pair of adjacent elements.
Track and return the minimum difference found.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        arr = []

        def dfs(node):
            if not node:
                return
            dfs(node.left)
            arr.append(node.val)
            dfs(node.right)

        dfs(root)
        res = arr[1] - arr[0]
        for i in range(2, len(arr)):
            res = min(res, arr[i] - arr[i - 1])
        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int minDiffInBST(TreeNode root) {
        List<Integer> arr = new ArrayList<>();

        dfs(root, arr);
        int res = arr.get(1) - arr.get(0);
        for (int i = 2; i < arr.size(); i++) {
            res = Math.min(res, arr.get(i) - arr.get(i - 1));
        }
        return res;
    }

    private void dfs(TreeNode node, List<Integer> arr) {
        if (node == null) {
            return;
        }
        dfs(node.left, arr);
        arr.add(node.val);
        dfs(node.right, arr);
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        vector<int> arr;
        dfs(root, arr);

        int res = arr[1] - arr[0];
        for (int i = 2; i < arr.size(); i++) {
            res = min(res, arr[i] - arr[i - 1]);
        }
        return res;
    }

private:
    void dfs(TreeNode* node, vector<int>& arr) {
        if (!node) return;
        dfs(node->left, arr);
        arr.push_back(node->val);
        dfs(node->right, arr);
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    minDiffInBST(root) {
        const arr = [];

        const dfs = (node) => {
            if (!node) return;
            dfs(node.left);
            arr.push(node.val);
            dfs(node.right);
        };

        dfs(root);
        let res = arr[1] - arr[0];
        for (let i = 2; i < arr.length; i++) {
            res = Math.min(res, arr[i] - arr[i - 1]);
        }
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MinDiffInBST(TreeNode root) {
        List<int> arr = new List<int>();
        Dfs(root, arr);

        int res = arr[1] - arr[0];
        for (int i = 2; i < arr.Count; i++) {
            res = Math.Min(res, arr[i] - arr[i - 1]);
        }
        return res;
    }

    private void Dfs(TreeNode node, List<int> arr) {
        if (node == null) return;
        Dfs(node.left, arr);
        arr.Add(node.val);
        Dfs(node.right, arr);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDiffInBST(root *TreeNode) int {
    var arr []int

    var dfs func(node *TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            return
        }
        dfs(node.Left)
        arr = append(arr, node.Val)
        dfs(node.Right)
    }

    dfs(root)
    res := arr[1] - arr[0]
    for i := 2; i < len(arr); i++ {
        res = min(res, arr[i]-arr[i-1])
    }
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun minDiffInBST(root: TreeNode?): Int {
        val arr = mutableListOf<Int>()

        fun dfs(node: TreeNode?) {
            if (node == null) return
            dfs(node.left)
            arr.add(node.`val`)
            dfs(node.right)
        }

        dfs(root)
        var res = arr[1] - arr[0]
        for (i in 2 until arr.size) {
            res = minOf(res, arr[i] - arr[i - 1])
        }
        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func minDiffInBST(_ root: TreeNode?) -> Int {
        var arr = [Int]()

        func dfs(_ node: TreeNode?) {
            guard let node = node else { return }
            dfs(node.left)
            arr.append(node.val)
            dfs(node.right)
        }

        dfs(root)
        var res = arr[1] - arr[0]
        for i in 2..<arr.count {
            res = min(res, arr[i] - arr[i - 1])
        }
        return res
    }
}

impl Solution {
    pub fn min_diff_in_bst(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut arr = Vec::new();
        Self::dfs(&root, &mut arr);
        let mut res = arr[1] - arr[0];
        for i in 2..arr.len() {
            res = res.min(arr[i] - arr[i - 1]);
        }
        res
    }

    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, arr: &mut Vec<i32>) {
        if let Some(n) = node {
            let n = n.borrow();
            Self::dfs(&n.left, arr);
            arr.push(n.val);
            Self::dfs(&n.right, arr);
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Inorder Traversal (Space Optimized)

Intuition

Instead of storing all values in an array and then finding the minimum difference, we can compute the answer during the traversal itself. We keep track of the previously visited node during the inorder walk. At each step, we compare the current node's value with the previous node's value (since they are consecutive in sorted order) and update the minimum difference on the fly.

Algorithm

Maintain a prev pointer to track the previously visited node during inorder traversal.
Initialize res to infinity.
Perform inorder traversal:
- Recurse on the left subtree.
- If prev exists, update res with min(res, current.val - prev.val).
- Set prev to the current node.
- Recurse on the right subtree.
Return res.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        prev, res = None, float("inf")

        def dfs(node):
            nonlocal prev, res
            if not node:
                return

            dfs(node.left)
            if prev:
                res = min(res, node.val - prev.val)
            prev = node
            dfs(node.right)

        dfs(root)
        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private TreeNode prev = null;
    private int res = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        dfs(root);
        return res;
    }

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

        dfs(node.left);
        if (prev != null) {
            res = Math.min(res, node.val - prev.val);
        }
        prev = node;
        dfs(node.right);
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        TreeNode* prev = nullptr;
        int res = INT_MAX;

        dfs(root, prev, res);
        return res;
    }

private:
    void dfs(TreeNode* node, TreeNode*& prev, int& res) {
        if (!node) return;

        dfs(node->left, prev, res);
        if (prev) {
            res = min(res, node->val - prev->val);
        }
        prev = node;
        dfs(node->right, prev, res);
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    minDiffInBST(root) {
        let prev = null;
        let res = Infinity;

        const dfs = (node) => {
            if (!node) return;

            dfs(node.left);
            if (prev !== null) {
                res = Math.min(res, node.val - prev.val);
            }
            prev = node;
            dfs(node.right);
        };

        dfs(root);
        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    private TreeNode prev = null;
    private int res = int.MaxValue;

    public int MinDiffInBST(TreeNode root) {
        Dfs(root);
        return res;
    }

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

        Dfs(node.left);
        if (prev != null) {
            res = Math.Min(res, node.val - prev.val);
        }
        prev = node;
        Dfs(node.right);
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDiffInBST(root *TreeNode) int {
    var prev *TreeNode
    res := math.MaxInt32

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

        dfs(node.Left)
        if prev != nil {
            res = min(res, node.Val-prev.Val)
        }
        prev = node
        dfs(node.Right)
    }

    dfs(root)
    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    private var prev: TreeNode? = null
    private var res = Int.MAX_VALUE

    fun minDiffInBST(root: TreeNode?): Int {
        dfs(root)
        return res
    }

    private fun dfs(node: TreeNode?) {
        if (node == null) return

        dfs(node.left)
        prev?.let {
            res = minOf(res, node.`val` - it.`val`)
        }
        prev = node
        dfs(node.right)
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func minDiffInBST(_ root: TreeNode?) -> Int {
        var prev: TreeNode? = nil
        var res = Int.max

        func dfs(_ node: TreeNode?) {
            guard let node = node else { return }

            dfs(node.left)
            if let p = prev {
                res = min(res, node.val - p.val)
            }
            prev = node
            dfs(node.right)
        }

        dfs(root)
        return res
    }
}

impl Solution {
    pub fn min_diff_in_bst(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut prev = None;
        let mut res = i32::MAX;
        Self::dfs(&root, &mut prev, &mut res);
        res
    }

    fn dfs(node: &Option<Rc<RefCell<TreeNode>>>, prev: &mut Option<i32>, res: &mut i32) {
        if let Some(n) = node {
            let n = n.borrow();
            Self::dfs(&n.left, prev, res);
            if let Some(p) = *prev {
                *res = (*res).min(n.val - p);
            }
            *prev = Some(n.val);
            Self::dfs(&n.right, prev, res);
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

4. Iterative DFS (Inorder Traversal)

Intuition

The recursive inorder traversal can be converted to an iterative version using an explicit stack. This avoids recursion overhead and gives us more control over the traversal. The logic remains the same: we visit nodes in sorted order and compare each node with its predecessor.

Algorithm

Initialize an empty stack and set cur to the root. Maintain prev to track the previous node.
While the stack is not empty or cur is not null:
- Push all left descendants of cur onto the stack.
- Pop a node from the stack.
- If prev exists, update the minimum difference.
- Set prev to the current node and move cur to the right child.
Return the minimum difference found.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        stack, prev, res = [], None, float("inf")
        cur = root

        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left

            cur = stack.pop()
            if prev:
                res = min(res, cur.val - prev.val)
            prev = cur
            cur = cur.right

        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int minDiffInBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode prev = null;
        int res = Integer.MAX_VALUE;
        TreeNode cur = root;

        while (!stack.isEmpty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (prev != null) {
                res = Math.min(res, cur.val - prev.val);
            }
            prev = cur;
            cur = cur.right;
        }

        return res;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* prev = nullptr;
        TreeNode* cur = root;
        int res = INT_MAX;

        while (!st.empty() || cur) {
            while (cur) {
                st.push(cur);
                cur = cur->left;
            }

            cur = st.top();
            st.pop();
            if (prev) {
                res = min(res, cur->val - prev->val);
            }
            prev = cur;
            cur = cur->right;
        }

        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    minDiffInBST(root) {
        let stack = [];
        let prev = null;
        let res = Infinity;
        let cur = root;

        while (stack.length > 0 || cur !== null) {
            while (cur !== null) {
                stack.push(cur);
                cur = cur.left;
            }

            cur = stack.pop();
            if (prev !== null) {
                res = Math.min(res, cur.val - prev.val);
            }
            prev = cur;
            cur = cur.right;
        }

        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MinDiffInBST(TreeNode root) {
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode prev = null;
        int res = int.MaxValue;
        TreeNode cur = root;

        while (stack.Count > 0 || cur != null) {
            while (cur != null) {
                stack.Push(cur);
                cur = cur.left;
            }

            cur = stack.Pop();
            if (prev != null) {
                res = Math.Min(res, cur.val - prev.val);
            }
            prev = cur;
            cur = cur.right;
        }

        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDiffInBST(root *TreeNode) int {
    stack := []*TreeNode{}
    var prev *TreeNode
    res := math.MaxInt32
    cur := root

    for len(stack) > 0 || cur != nil {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }

        cur = stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if prev != nil {
            res = min(res, cur.Val-prev.Val)
        }
        prev = cur
        cur = cur.Right
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun minDiffInBST(root: TreeNode?): Int {
        val stack = ArrayDeque<TreeNode>()
        var prev: TreeNode? = null
        var res = Int.MAX_VALUE
        var cur = root

        while (stack.isNotEmpty() || cur != null) {
            while (cur != null) {
                stack.addLast(cur)
                cur = cur.left
            }

            cur = stack.removeLast()
            prev?.let {
                res = minOf(res, cur!!.`val` - it.`val`)
            }
            prev = cur
            cur = cur?.right
        }

        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func minDiffInBST(_ root: TreeNode?) -> Int {
        var stack = [TreeNode]()
        var prev: TreeNode? = nil
        var res = Int.max
        var cur = root

        while !stack.isEmpty || cur != nil {
            while cur != nil {
                stack.append(cur!)
                cur = cur?.left
            }

            cur = stack.removeLast()
            if let p = prev {
                res = min(res, cur!.val - p.val)
            }
            prev = cur
            cur = cur?.right
        }

        return res
    }
}

impl Solution {
    pub fn min_diff_in_bst(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
        let mut prev: Option<i32> = None;
        let mut res = i32::MAX;
        let mut cur = root;

        while !stack.is_empty() || cur.is_some() {
            while let Some(node) = cur {
                cur = node.borrow().left.clone();
                stack.push(node);
            }

            let node = stack.pop().unwrap();
            let val = node.borrow().val;
            if let Some(p) = prev {
                res = res.min(val - p);
            }
            prev = Some(val);
            cur = node.borrow().right.clone();
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Morris Traversal

Intuition

Morris traversal allows us to perform inorder traversal without using a stack or recursion, achieving O(1) extra space. The idea is to temporarily modify the tree by creating links from predecessor nodes back to their successors, allowing us to navigate the tree without additional memory. We traverse the tree, comparing consecutive values as before.

Algorithm

Initialize cur to the root and prevVal to track the value of the previous node visited.
While cur is not null:
- If cur has no left child:
  - Process cur (compare with prevVal and update minimum).
  - Update prevVal and move to the right child.
- Else, find the inorder predecessor (rightmost node in left subtree):
  - If the predecessor's right pointer is null, set it to cur and move left.
  - If the predecessor's right pointer is cur, restore it to null, process cur, update prevVal, and move right.
Return the minimum difference found.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        prevVal = res = float("inf")
        cur = root

        while cur:
            if not cur.left:
                if prevVal != float("inf"):
                    res = min(res, cur.val - prevVal)
                prevVal = cur.val
                cur = cur.right
            else:
                prev = cur.left
                while prev.right and prev.right != cur:
                    prev = prev.right

                if not prev.right:
                    prev.right = cur
                    cur = cur.left
                else:
                    prev.right = None
                    if prevVal != float("inf"):
                        res = min(res, cur.val - prevVal)
                    prevVal = cur.val
                    cur = cur.right

        return res

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int minDiffInBST(TreeNode root) {
        int prevVal = Integer.MAX_VALUE, res = Integer.MAX_VALUE;
        TreeNode cur = root;

        while (cur != null) {
            if (cur.left == null) {
                if (prevVal != Integer.MAX_VALUE) {
                    res = Math.min(res, cur.val - prevVal);
                }
                prevVal = cur.val;
                cur = cur.right;
            } else {
                TreeNode prev = cur.left;
                while (prev.right != null && prev.right != cur) {
                    prev = prev.right;
                }

                if (prev.right == null) {
                    prev.right = cur;
                    cur = cur.left;
                } else {
                    prev.right = null;
                    if (prevVal != Integer.MAX_VALUE) {
                        res = Math.min(res, cur.val - prevVal);
                    }
                    prevVal = cur.val;
                    cur = cur.right;
                }
            }
        }

        return res;
    }
}

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDiffInBST(TreeNode* root) {
        int prevVal = INT_MAX, res = INT_MAX;
        TreeNode* cur = root;

        while (cur) {
            if (!cur->left) {
                if (prevVal != INT_MAX) {
                    res = min(res, cur->val - prevVal);
                }
                prevVal = cur->val;
                cur = cur->right;
            } else {
                TreeNode* prev = cur->left;
                while (prev->right && prev->right != cur) {
                    prev = prev->right;
                }

                if (!prev->right) {
                    prev->right = cur;
                    cur = cur->left;
                } else {
                    prev->right = nullptr;
                    if (prevVal != INT_MAX) {
                        res = min(res, cur->val - prevVal);
                    }
                    prevVal = cur->val;
                    cur = cur->right;
                }
            }
        }

        return res;
    }
};

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     constructor(val = 0, left = null, right = null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    /**
     * @param {TreeNode} root
     * @return {number}
     */
    minDiffInBST(root) {
        let prevVal = Infinity,
            res = Infinity;
        let cur = root;

        while (cur !== null) {
            if (cur.left === null) {
                if (prevVal !== Infinity) {
                    res = Math.min(res, cur.val - prevVal);
                }
                prevVal = cur.val;
                cur = cur.right;
            } else {
                let prev = cur.left;
                while (prev.right !== null && prev.right !== cur) {
                    prev = prev.right;
                }

                if (prev.right === null) {
                    prev.right = cur;
                    cur = cur.left;
                } else {
                    prev.right = null;
                    if (prevVal !== Infinity) {
                        res = Math.min(res, cur.val - prevVal);
                    }
                    prevVal = cur.val;
                    cur = cur.right;
                }
            }
        }

        return res;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public int MinDiffInBST(TreeNode root) {
        int prevVal = int.MaxValue, res = int.MaxValue;
        TreeNode cur = root;

        while (cur != null) {
            if (cur.left == null) {
                if (prevVal != int.MaxValue) {
                    res = Math.Min(res, cur.val - prevVal);
                }
                prevVal = cur.val;
                cur = cur.right;
            } else {
                TreeNode prev = cur.left;
                while (prev.right != null && prev.right != cur) {
                    prev = prev.right;
                }

                if (prev.right == null) {
                    prev.right = cur;
                    cur = cur.left;
                } else {
                    prev.right = null;
                    if (prevVal != int.MaxValue) {
                        res = Math.Min(res, cur.val - prevVal);
                    }
                    prevVal = cur.val;
                    cur = cur.right;
                }
            }
        }

        return res;
    }
}

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func minDiffInBST(root *TreeNode) int {
    prevVal := math.MaxInt32
    res := math.MaxInt32
    cur := root

    for cur != nil {
        if cur.Left == nil {
            if prevVal != math.MaxInt32 {
                res = min(res, cur.Val-prevVal)
            }
            prevVal = cur.Val
            cur = cur.Right
        } else {
            prev := cur.Left
            for prev.Right != nil && prev.Right != cur {
                prev = prev.Right
            }

            if prev.Right == nil {
                prev.Right = cur
                cur = cur.Left
            } else {
                prev.Right = nil
                if prevVal != math.MaxInt32 {
                    res = min(res, cur.Val-prevVal)
                }
                prevVal = cur.Val
                cur = cur.Right
            }
        }
    }

    return res
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun minDiffInBST(root: TreeNode?): Int {
        var prevVal = Int.MAX_VALUE
        var res = Int.MAX_VALUE
        var cur = root

        while (cur != null) {
            if (cur.left == null) {
                if (prevVal != Int.MAX_VALUE) {
                    res = minOf(res, cur.`val` - prevVal)
                }
                prevVal = cur.`val`
                cur = cur.right
            } else {
                var prev = cur.left
                while (prev?.right != null && prev.right != cur) {
                    prev = prev.right
                }

                if (prev?.right == null) {
                    prev?.right = cur
                    cur = cur.left
                } else {
                    prev.right = null
                    if (prevVal != Int.MAX_VALUE) {
                        res = minOf(res, cur.`val` - prevVal)
                    }
                    prevVal = cur.`val`
                    cur = cur.right
                }
            }
        }

        return res
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */
class Solution {
    func minDiffInBST(_ root: TreeNode?) -> Int {
        var prevVal = Int.max
        var res = Int.max
        var cur = root

        while cur != nil {
            if cur!.left == nil {
                if prevVal != Int.max {
                    res = min(res, cur!.val - prevVal)
                }
                prevVal = cur!.val
                cur = cur!.right
            } else {
                var prev = cur!.left
                while prev!.right != nil && prev!.right !== cur {
                    prev = prev!.right
                }

                if prev!.right == nil {
                    prev!.right = cur
                    cur = cur!.left
                } else {
                    prev!.right = nil
                    if prevVal != Int.max {
                        res = min(res, cur!.val - prevVal)
                    }
                    prevVal = cur!.val
                    cur = cur!.right
                }
            }
        }

        return res
    }
}

impl Solution {
    pub fn min_diff_in_bst(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        // Morris traversal is not idiomatic in Rust with Rc<RefCell<TreeNode>>
        // due to shared ownership constraints. Use iterative inorder instead.
        let mut stack: Vec<Rc<RefCell<TreeNode>>> = Vec::new();
        let mut prev_val = i32::MAX;
        let mut res = i32::MAX;
        let mut cur = root;

        while !stack.is_empty() || cur.is_some() {
            while let Some(node) = cur {
                cur = node.borrow().left.clone();
                stack.push(node);
            }
            let node = stack.pop().unwrap();
            let val = node.borrow().val;
            if prev_val != i32::MAX {
                res = res.min(val - prev_val);
            }
            prev_val = val;
            cur = node.borrow().right.clone();
        }

        res
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.

Common Pitfalls

Not Leveraging BST Properties

The most common mistake is treating this as a generic binary tree problem and comparing all pairs of nodes, resulting in O(n^2) time complexity. The BST property guarantees that inorder traversal produces a sorted sequence, so the minimum difference must occur between consecutive elements. Always use inorder traversal to reduce complexity to O(n).

Comparing Non-Adjacent Elements

In a sorted sequence, the minimum difference is always between adjacent elements. Some implementations incorrectly compare non-adjacent pairs or track global minimum/maximum values instead of the previous node, missing the optimal answer or overcomplicating the solution.