🤖 leetcode 783. Minimum Distance Between BST Nodes | medium | tree | javascript

🗒️ Problems

783. Minimum Distance Between BST Nodes - Leetcode 783

Given the root of a Binary Search Tree (BST),
return the minimum difference between the values of any two different nodes in the tree.

Input: root = [4,2,6,1,3]
Output: 1

🤔 Understand problem

• the minimum difference between the values of any two different nodes in the tree.
• not only for the adjacent nodes.

🤦‍♂️ First attempt

• In BST, in-order traversal makes the ascending sorted array.
• Therefore after in-order traversal, calculate the minimum difference between values.

var minDiffInBST = function (root) {
  const arr = [];

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

    dfs(node.left);
    arr.push(node.val);
    dfs(node.right);
  };

  dfs(root);

  let min = Infinity;
  for (let i = 1; i < arr.length; i += 1) {
    min = Math.min(min, arr[i] - arr[i - 1]);
  }

  return min;
};

🥳 Think differently

• Actually, the nature of BST tree is NOT used fully.
• Can I use only the recursive call ?

✨ Idea

• The minimum difference can only occur between the next nodes, which can reside in the different node.
• The fact that the in-order traversal makes the ascending sorted array means that it always visit the previous node, and then visit the next larger value node.
• Can we calculate the difference between the current node and the previous precessor node in place ?

⬇️💡 Save precessor

// visit left nodes

precessor =  [1] current = 2
precessor =  [2,1,3] current = 3
precessor =  [3] current = 4
precessor =  [4,2,6,1,3] current = 6

var minDiffInBST = function (root) {
  let precessor = null;
  let min = Infinity;

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

    dfs(node.left);

    precessor = node;

    dfs(node.right);
  };

  dfs(root);

  return min;
};

⬇️💡 Calculate the difference and update minimum value

• Calculate the difference between the previous precessor and current node node.val.
• Update the minimum value.

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

        dfs(node.left);

        if (precessor) min = Math.min(min, node.val - precessor.val);
        precessor = node;

        dfs(node.right);
    }
};

⬇️🔥 My 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)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDiffInBST = function (root) {
  let precessor = null;
  let min = Infinity;

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

    dfs(node.left);

    if (precessor) min = Math.min(min, node.val - precessor.val);
    precessor = node;

    dfs(node.right);
  };

  dfs(root);

  return min;
};

🙆‍♂️ Time complexity: O(n)

• The recursive function calls only once for each node in the tree.