530. Minimum Absolute Difference in BST
Model: qwen2.5-coder:14b
Topics: Tree
FAANG asked: 1
Acceptance rate: 55.0%
Problem Breakdown
The problem requires finding the minimum absolute difference between values of any two nodes in a binary search tree (BST). The BST contains non-negative values, and there are at least two nodes. The goal is to determine the smallest possible difference between any pair of node values.
Inputs:
- A binary search tree with non-negative integer values.
- At least two nodes in the tree.
Outputs:
- An integer representing the minimum absolute difference between any two node values.
Implicit Constraints or Edge Cases:
- The BST property must be maintained, where for each node, all values in its left subtree are less than the node’s value, and all values in its right subtree are greater.
- The tree is guaranteed to have at least two nodes, so no special handling for empty trees is required.
Intuition
A brute-force approach would involve comparing every pair of nodes in the tree, resulting in a time complexity of (O(n^2)), where (n) is the number of nodes. This is inefficient for large trees.
The key insight is to leverage the properties of a BST. An in-order traversal of a BST visits nodes in ascending order. By performing an in-order traversal and keeping track of the previous node’s value, we can compute the absolute difference between consecutive nodes, which will give us the minimum absolute difference efficiently.
Approach
- In-Order Traversal: Perform an in-order traversal of the BST to visit nodes in ascending order.
- Track Previous Node: Maintain a variable to store the value of the previously visited node during the traversal.
- Compute Differences: For each node, compute the absolute difference between its value and the previous node’s value. Update the minimum difference if the current difference is smaller.
- Return Result: After traversing all nodes, return the smallest computed difference.
Complexity Analysis
- Time Complexity: (O(n)), where (n) is the number of nodes in the tree. This is because we visit each node exactly once during the in-order traversal.
- Space Complexity: (O(h)), where (h) is the height of the tree. This is due to the recursion stack used for the in-order traversal. In the worst case, this can be (O(n)) for a skewed tree.
Solution
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def getMinimumDifference(root: TreeNode) -> int:
# Initialize the minimum difference to a large number
min_diff = float('inf')
# Variable to store the value of the previous node during in-order traversal
prev_val = None
def inorder_traversal(node):
nonlocal min_diff, prev_val
if not node:
return
# Traverse the left subtree
inorder_traversal(node.left)
# Process the current node
if prev_val is not None:
# Update the minimum difference
min_diff = min(min_diff, abs(node.val - prev_val))
# Update the previous node's value
prev_val = node.val
# Traverse the right subtree
inorder_traversal(node.right)
# Start in-order traversal from the root
inorder_traversal(root)
return min_diff
Edge Cases Handled
- Balanced Tree: The algorithm works efficiently for balanced trees where the height is (O(\log n)).
- Skewed Tree (e.g., a linked list): The space complexity degrades to (O(n)) due to the recursion stack, but the time complexity remains (O(n)).
- All Nodes Have Same Value: The minimum difference will be 0 since all nodes have the same value.
- Consecutive Values in In-Order Traversal: The algorithm correctly identifies the smallest difference between consecutive values during the traversal.