algoadvance

The problem requires you to find the minimum difference between the values of any two different nodes in a Binary Search Tree (BST).

The structure of BST ensures that the left subtree of a node contains only nodes with keys less than the node’s key, and the right subtree only contains nodes with keys greater than the node’s key.

Clarifying Questions:

1. Can the BST contain duplicate values?
   • No, by definition a BST does not contain duplicate values.
2. What is the range of values for the nodes in the BST?
   • Nodes’ values are generally within the range of typical 32-bit integers.
3. Is the BST guaranteed to have at least two nodes?
   • Yes, because we need to find the minimum distance between any two nodes, there must be at least two nodes.

Strategy:

1. Inorder Traversal: An inorder traversal of a BST gives nodes in sorted order.

2. Store Values: As we perform an inorder traversal, we will keep track of the previous node’s value.

3. Calculate Min Difference: By comparing the current node’s value with the previous node’s value and updating our minimum difference whenever we find a smaller one.

Code:

Here is the Python function to solve this problem:

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

def minDiffInBST(root: TreeNode) -> int:
    # Initialize previous value as None and min_diff as a large number
    pre_val = None
    min_diff = float('inf')
    
    def inorder(node: TreeNode):
        nonlocal pre_val, min_diff
        if node:
            # Traverse the left subtree
            inorder(node.left)
            
            # If previous value exists, calculate the difference and update min_diff
            if pre_val is not None:
                min_diff = min(min_diff, node.val - pre_val)
                
            # Update the previous value to the current node's value
            pre_val = node.val
            
            # Traverse the right subtree
            inorder(node.right)
    
    # Start inorder traversal from the root
    inorder(root)
    
    return min_diff

Explanation:

1. TreeNode Class: This is the basic structure of a node in a BST, with attributes val, left, and right.

2. minDiffInBST Function: Initializes pre_val to None and min_diff to infinity. The nested inorder function performs an in-order traversal of the BST.

3. Inorder Traversal:
   • As we traverse the left subtree, we keep updating our pre_val with the current node’s value.
   • For each newly visited node, we calculate the difference between the current node’s value and pre_val.
   • Update the min_diff whenever we find a smaller difference.
4. Return Result: After the complete traversal, we return min_diff, which holds the smallest difference between any two nodes in the BST.

Time Complexity:

• Traversal: The function performs an in-order traversal over the nodes of the BST, visiting each node exactly once.

• Thus, the time complexity is O(N), where N is the number of nodes in the BST.

• Space Complexity: The extra space used is primarily for the recursion stack during the in-order traversal, so the space complexity is O(H), where H is the height of the tree. In the worst case, H could be N (for a completely unbalanced tree), but for a balanced tree, it would be log(N).

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?