Skip to main content

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​

/**
 * 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;
}

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

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