Minimum Distance Between BST Nodes Interview Question for Meta

## Minimum Difference Between BST Nodes

This problem asks us to find the minimum difference between the values of any two different nodes in a Binary Search Tree (BST). The key property of a BST is that for any node, all nodes in its left subtree have values less than the node's value, and all nodes in its right subtree have values greater than the node's value.

### 1. Naive Approach

A simple, but not very efficient, approach would be to traverse the BST and store all the node values in a list. Then, sort the list and iterate through it to find the minimum difference between adjacent elements.

**Code (Python):**

```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def min_diff_naive(root):
    values = []

    def inorder_traversal(node):
        if not node:
            return
        inorder_traversal(node.left)
        values.append(node.val)
        inorder_traversal(node.right)

    inorder_traversal(root)
    values.sort()
    min_diff = float('inf')
    for i in range(1, len(values)):
        min_diff = min(min_diff, values[i] - values[i - 1])
    return min_diff

2. Optimal Approach

A more efficient approach leverages the inherent ordering of a BST. By performing an inorder traversal, we can visit the nodes in sorted order. We can then keep track of the previous node visited and calculate the difference between the current node and the previous node. The minimum of these differences will be the answer.

Code (Python):

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def min_diff_bst(root):
    min_diff = float('inf')
    prev = None

    def inorder_traversal(node):
        nonlocal min_diff, prev
        if not node:
            return

        inorder_traversal(node.left)

        if prev is not None:
            min_diff = min(min_diff, node.val - prev.val)

        prev = node
        inorder_traversal(node.right)

    inorder_traversal(root)
    return min_diff

3. Example

Consider the following BST:

The inorder traversal would visit the nodes in the order: 1, 2, 3, 4, 6.

The differences would be:

2 - 1 = 1
3 - 2 = 1
4 - 3 = 1
6 - 4 = 2

The minimum difference is 1.

4. Big(O) Run-time Analysis

Naive Approach: O(N log N), where N is the number of nodes in the tree. This is due to the sorting step. The inorder traversal is O(N), but the sorting dominates the time complexity.
Optimal Approach: O(N), where N is the number of nodes in the tree. The inorder traversal visits each node once.

5. Big(O) Space Usage Analysis

Naive Approach: O(N), where N is the number of nodes in the tree. This is because we store all the node values in a list.
Optimal Approach: O(H), where H is the height of the tree. This is due to the recursion stack during the inorder traversal. In the worst case (skewed tree), H can be equal to N, resulting in O(N) space complexity. In the best case (balanced tree), H is log N, resulting in O(log N) space complexity.

6. Edge Cases

Empty Tree: If the tree is empty (root is None), the function should return float('inf') or raise an exception, depending on the requirements. In the code above, the traversal does nothing if the node is None.
Only One Node: If the tree only contains the root node, there are no two nodes to calculate the difference from, so return float('inf').
Negative Values: The provided constraints state that 0 <= Node.val <= 10^5, so negative values are not a concern. However, if negative values are possible, the algorithm would still work correctly.
Duplicate Values: Duplicate values in the BST will result in a minimum difference of 0 if they are adjacent in the inorder traversal.