Minimum Distance Between BST Nodes

Problem Source

Companies: Amazon, Google

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

Example :

Input: root = [5,3,7,1,4,null,null]

Output: 1

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

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

      5
    /   \
  3      7
 / \    
1   4  

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

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:

This problem is only solved by traversing through the whole tree. Best way to traverse this tree to find the correct output is in-order traversal.

In order traversal is one such type of traversal methods in which we can traverse the whole tree in a similar pattern. Sonce we have to find minimum distance between any two nodes, we have to remember the value of the last node we traversed to find the difference of it with the current node. We always have to keep the minimum value of the difference with us while traversing the tree.

Implementation

Java

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);
    }
}

Complexity Analysis:

• Time Complexity: O(N), N = Number of nodes in a tree.
• Space Complexity: O(H), H is the height of the tree.