Minimum Absolute Difference in BST
Problem Description
Question
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.
Example 1:
Input:root=[4,2,6,1,3]
Output: 1
Example 2:
Input:root=[1,0,48,null,null,12,49]
Output: 1
Constraints:
- The number of nodes in the tree is in the range [2, 104].
- 0 <= Node.val <= 105
Solve it on LeetCode
Approaches
1. Inorder Traversal with ArrayList
Intuition:
The Binary Search Tree (BST) property ensures that an inorder traversal of the tree will yield nodes in ascending order. By storing these nodes in a list during the traversal, we can then easily compute the minimum absolute difference between consecutive elements.
Steps:
- Perform an inorder traversal of the BST to get the nodes in sorted order.
- Store the values of the nodes in an
ArrayList. - Compute the minimum difference between adjacent elements in the list.
Code:
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes in the BST. We visit each node once.
- Space Complexity: O(N), due to the storage of the inorder traversal.
2. Inorder Traversal with Constant Space
Intuition:
Instead of storing the entire list of values, we can maintain a running track of the previously visited node and compute the minimum difference on-the-fly. This approach utilizes the properties of inorder traversal while reducing space usage.
Steps:
- Use a recursive function for the inorder traversal.
- Keep track of the previous node's value.
- Update the minimum difference during traversal without using additional space for storage.
Code:
Complexity Analysis
- Time Complexity: O(N), where N is the number of nodes in the BST. Each node is visited once.
- Space Complexity: O(H), where H is the height of the tree, due to the recursion stack. This space is not used for data storage, but for function calls in the call stack.