Naive Solution: Brute Force

The most straightforward approach is to traverse the tree, store the values of all nodes in an array, and then find the minimum difference between any two values in the array.

1. Traverse the tree: Perform an inorder traversal to collect all node values into a list.
2. Calculate minimum difference: Iterate through all pairs of values in the list and find the minimum absolute difference.

Code (Python):

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

def getMinimumDifference(root):
    values = []

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

    inorder(root)
    min_diff = float('inf')
    for i in range(len(values)):
        for j in range(i + 1, len(values)):
            min_diff = min(min_diff, abs(values[i] - values[j]))
    return min_diff

Time Complexity: O(N²), where N is the number of nodes in the tree. This is because we have nested loops to compare all pairs of values.

Space Complexity: O(N), where N is the number of nodes in the tree. This is due to storing the node values in a list.

Optimal Solution: Inorder Traversal

Since it's a Binary Search Tree (BST), an inorder traversal will give us the node values in sorted order. We can then find the minimum difference by comparing adjacent values in the sorted order.

1. Inorder Traversal: Perform an inorder traversal of the BST.
2. Track Previous Value: Keep track of the previously visited node's value during the traversal.
3. Calculate Minimum Difference: At each node, calculate the difference between the current node's value and the previous value. Update the minimum difference accordingly.

Code (Python):

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

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

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

        inorder(node.left)

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

        prev = node.val
        inorder(node.right)

    inorder(root)
    return min_diff

Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node once during the inorder traversal.

Space Complexity: O(H), where H is the height of the tree. This is due to the recursive call stack during inorder traversal. In the worst case (skewed tree), H can be equal to N, and in the best case (balanced tree), H can be log(N).

Edge Cases:

• Empty Tree: The problem states that the number of nodes is in the range [2, 100]. So we don't need to consider the case where the tree is empty. However, it is still good practice to confirm any constraints and edge cases like this with the interviewer.
• Only Two Nodes: The algorithm should correctly handle the case when there are only two nodes in the tree. In this case, the minimum difference will simply be the absolute difference between the two node values.