Minimum Difference in Binary Search Tree

Given a binary search tree, return the minimum difference between any two nodes in the tree.

Example(s)

Example 1:

Tree:
        2
       / \
      1   3
Output: 1

Example 2:

Tree:
        29
       /  \
      17   50
     /    / \
    1    42  59
Output: 8

Example 3:

Tree:
        2
         \
         100
Output: 98

Solution

JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

/**
 * Find minimum difference between any two nodes in a BST
 * @param {TreeNode} root - Root of the BST
 * @return {number} - Minimum difference
 */
function minDiffInBST(root) {
  let prev = null;
  let minDiff = Infinity;
  
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    if (prev !== null) {
      minDiff = Math.min(minDiff, node.val - prev);
    }
    prev = node.val;
    inorder(node.right);
  }
  
  inorder(root);
  return minDiff;
}

Python Solution

from typing import Optional

# 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

def min_diff_in_bst(root: Optional[TreeNode]) -> int:
    """
    Find minimum difference between any two nodes in a BST
    
    Args:
        root: Root of the BST
        
    Returns:
        int: Minimum difference
    """
    prev = [None]  # Use list to allow modification in nested function
    min_diff = [float('inf')]
    
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        if prev[0] is not None:
            min_diff[0] = min(min_diff[0], node.val - prev[0])
        prev[0] = node.val
        inorder(node.right)
    
    inorder(root)
    return min_diff[0]

Complexity

• Time Complexity: O(n) - Where n is the number of nodes, as we visit each node once
• Space Complexity: O(h) - Where h is the height of the tree, due to recursion stack

Interactive Code Runner

Test the Solution

JavaScript Solution

JavaScript Minimum Difference Solution

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

/**
* Find minimum difference between any two nodes in a BST
* @param {TreeNode} root - Root of the BST
* @return {number} - Minimum difference
*/
function minDiffInBST(root) {
let prev = null;
let minDiff = Infinity;

function inorder(node) {
  if (!node) return;
  inorder(node.left);
  if (prev !== null) {
    minDiff = Math.min(minDiff, node.val - prev);
  }
  prev = node.val;
  inorder(node.right);
}

inorder(root);
return minDiff;
}

// Test case 1: [2,1,3]
const tree1 = new TreeNode(2);
tree1.left = new TreeNode(1);
tree1.right = new TreeNode(3);

// Test case 2: [29,17,50,1,null,42,59]
const tree2 = new TreeNode(29);
tree2.left = new TreeNode(17);
tree2.right = new TreeNode(50);
tree2.left.left = new TreeNode(1);
tree2.right.left = new TreeNode(42);
tree2.right.right = new TreeNode(59);

// Test case 3: [2,null,100]
const tree3 = new TreeNode(2);
tree3.right = new TreeNode(100);

// Test cases
console.log(minDiffInBST(tree1)); // 1
console.log(minDiffInBST(tree2)); // 1
console.log(minDiffInBST(null)); // Infinity

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python Minimum Difference BST Solution

from typing import Optional

# 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

def min_diff_in_bst(root: Optional[TreeNode]) -> int:
  """
  Find minimum difference between any two nodes in a BST
  
  Args:
      root: Root of the BST
      
  Returns:
      int: Minimum difference
  """
  prev = [None]
  min_diff = [float('inf')]
  
  def inorder(node):
      if not node:
          return
      inorder(node.left)
      if prev[0] is not None:
          min_diff[0] = min(min_diff[0], node.val - prev[0])
      prev[0] = node.val
      inorder(node.right)
  
  inorder(root)
  return min_diff[0]

# Test case 1: [2,1,3]
tree1 = TreeNode(2)
tree1.left = TreeNode(1)
tree1.right = TreeNode(3)

# Test case 2: [29,17,50,1,null,42,59]
tree2 = TreeNode(29)
tree2.left = TreeNode(17)
tree2.right = TreeNode(50)
tree2.left.left = TreeNode(1)
tree2.right.left = TreeNode(42)
tree2.right.right = TreeNode(59)

# Test case 3: [2,null,100]
tree3 = TreeNode(2)
tree3.right = TreeNode(100)

# Test cases
print(min_diff_in_bst(tree1))  # 1
print(min_diff_in_bst(tree2))  # 1
print(min_diff_in_bst(None))  # float('inf')

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Takeaways

• In-order traversal ensures nodes are visited in ascending order, simplifying difference calculations
• Tracking previous value allows comparison with the current node to find minimum difference
• BST property guarantees adjacent nodes in in-order traversal have the smallest differences
• Edge cases include trees with two nodes or skewed trees
• O(n) time is optimal as all nodes must be visited to ensure minimum difference