grid47 Exploring patterns and algorithms
Sep 15, 2024
6 min read
Solution to LeetCode 530: Minimum Absolute Difference in BST Problem
Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
Problem
Approach
Steps
Complexity
Input: The input consists of the root of a Binary Search Tree, which is represented as a list of integers where each value represents a node in the tree. Null values indicate absent nodes.
Example: Input: root = [4,2,6,1,3]
Constraints:
• 2 <= The number of nodes in the tree <= 10^4
• 0 <= Node.val <= 10^5
Output: Return the smallest absolute difference between values of any two nodes in the tree.
Example: Output: 1
Constraints:
• The answer will always be a positive integer.
Goal: To find the minimum absolute difference between values of any two nodes in the BST.
Steps:
• Perform an in-order traversal of the BST. In-order traversal of a BST yields a sorted list of values.
• For each adjacent pair of values in this sorted list, calculate the absolute difference.
• Track the minimum difference encountered.
Goal: Constraints for this problem ensure that the tree has at least two nodes, and node values are within the valid range.
Steps:
• Node values are non-negative and less than or equal to 10^5.
• The number of nodes in the tree is between 2 and 10^4.
Assumptions:
• The input tree is a valid Binary Search Tree.
• The tree will contain at least two nodes.
• Input: Input: root = [4,2,6,1,3]
• Explanation: An in-order traversal of the BST gives the values [1, 2, 3, 4, 6]. The minimum absolute difference is 1, as the closest pair is (2, 3).
Approach: To solve this problem, we will leverage an in-order traversal of the BST to generate a sorted list of node values, from which we can easily calculate the minimum absolute difference.
Observations:
• In-order traversal of a BST results in a sorted list of values.
• The minimum absolute difference between two nodes will always be between two adjacent nodes in the sorted list.
Steps:
• Perform an in-order traversal of the tree to collect the node values in sorted order.
• Calculate the difference between each consecutive pair of values in the sorted list.
• Return the smallest difference encountered.
Empty Inputs:
• The tree has only one node (though this case is guaranteed not to happen due to the constraints).
Large Inputs:
• A tree with the maximum number of nodes (10^4 nodes).
Special Values:
• All nodes in the tree have the same value.
Constraints:
• Ensure correct handling of trees with multiple identical values.
Defines the `getMinimumDifference` function that calculates the minimum absolute difference between node values in a Binary Search Tree (BST). The function takes the root of the tree as an argument.
2 : Variable Initialization
TreeNode* prv =NULL; int ans = INT_MAX;
Initializes a pointer `prv` to track the previous node during traversal and a variable `ans` to store the minimum difference, initially set to the maximum possible value (`INT_MAX`).
3 : Stack Initialization
stack<TreeNode*> stk;
Creates a stack `stk` to assist with the in-order traversal of the tree. This stack helps simulate the recursion that would normally be used for tree traversal.
4 : While Loop, Tree Traversal
while(!stk.empty() || root) {
Starts the while loop that continues until the stack is empty and the current node (`root`) is NULL, ensuring all nodes are visited.
5 : Condition, Node Traversal
if(root) {
Checks if the current node (`root`) is not NULL, indicating there are still nodes to traverse in the tree.
6 : Push to Stack, Left Subtree
stk.push(root);
Pushes the current node onto the stack to keep track of the path. This is part of the in-order traversal.
7 : Move to Left Child
root = root->left;
Moves the current pointer to the left child of the current node, continuing the in-order traversal.
8 : Else Block, Backtrack
} else {
Executes when the current node is NULL, indicating that the left subtree has been fully traversed and it's time to process the current node.
9 : Pop from Stack
root = stk.top();
Pops the top element from the stack, which gives the node that is to be processed next in the in-order traversal.
10 : Pop Stack, Move to Next Node
stk.pop();
Removes the current node from the stack after processing it.
11 : Check Previous Node
if(prv !=NULL) {
Checks if the previous node (`prv`) is not NULL, ensuring that there is a valid comparison between the current node and the previous one.
12 : Calculate Minimum Difference
ans = min(ans, root->val - prv->val);
Calculates the minimum absolute difference between the current node's value and the previous node's value. If the difference is smaller than the current `ans`, it updates `ans`.
13 : Update Previous Node
prv = root;
Updates the `prv` pointer to the current node, as it will be used for the next comparison.
14 : Move to Right Child
root = root->right;
Moves the pointer to the right child of the current node to continue the in-order traversal.
15 : Return Minimum Difference
return ans;
Returns the minimum absolute difference between node values found during the traversal.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n) where n is the number of nodes in the tree, as we perform an in-order traversal and a single pass to calculate the differences.
Best Case: O(h)
Worst Case: O(n)
Description: The space complexity is O(n) in the worst case due to the recursion stack of the in-order traversal, where n is the number of nodes, and O(h) in the best case, where h is the height of the tree.
