Minimum Distance Between BST Nodes

Leetcode Problem 783: Minimum Distance Between BST Nodes

Problem Summary

Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two distinct nodes in the tree. (This is equivalent to the Minimum Absolute Difference problem.)

Constraints:

• The tree has between 2 and 100 nodes.
• Node values are non-negative integers up to 100,000.

Techniques

• Tree
• Depth-First Search
• Breadth-First Search
• Binary Search Tree
• Binary Tree

Solution

export class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null

    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val)
        this.left = (left === undefined ? null : left)
        this.right = (right === undefined ? null : right)
    }
}

function minDiffInBST(root: TreeNode | null): number {
    let stack: TreeNode[] = []
    let result: number[] = []
    let current = root
    let previous: number | null = null
    let min = Infinity

    while (current || stack.length > 0) {
        while (current) {
            stack.push(current)
            current = current.left
        }

        current = stack.pop()!

        if (previous !== null) {
            min = Math.min(min, current.val - previous)
        }

        previous = current.val
        current = current.right
    }

    return min
}