Minimum Distance (Difference) Between BST Nodes

Binary Search Tree

Almost same as Minimum Absolute Difference in BST

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

Example :

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

Output:
 1

Explanation:

Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

Note:

1. The size of the BST will be between 2 and 100.

2. The BST is always valid, each node's value is an integer, and each node's value is different.

Solution

In-order Traversal of BST output the node value in sorted order; using a global variable prev to store previous value for comparison.

https://leetcode.com/problems/minimum-distance-between-bst-nodes/solution/

Approach #1: Write to Array

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes in the tree. The complexity comes from the sorting operation.

• Space Complexity:O(N), the size ofvals.

class Solution {
    List<Integer> vals;
    public int minDiffInBST(TreeNode root) {
        vals = new ArrayList();
        dfs(root);

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i < vals.size() - 1; ++i)
            ans = Math.min(ans, vals.get(i+1) - vals.get(i));

        return ans;
    }

    public void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        vals.add(node.val);
        dfs(node.right);
    }
}

Approach #2: In-Order Traversal

In a binary search tree, an in-order traversal outputs the values of the tree in order. By remembering the previous value in this order, we could iterate over each possible difference, keeping the smallest one.

Complexity Analysis

• Time Complexity: O(N), whereNNis the number of nodes in the tree. We iterate over every node once.

• Space Complexity: O(H), whereHHis the height of the tree. This is the space used by the implicit call stack when callingdfs.

class Solution {
    Integer prev, ans;
    public int minDiffInBST(TreeNode root) {
        prev = null;
        ans = Integer.MAX_VALUE;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode node) {
        if (node == null) return;
        dfs(node.left);
        if (prev != null)
            ans = Math.min(ans, node.val - prev);
        prev = node.val;
        dfs(node.right);
    }
}

Minimum Distance Between BST Nodes