Minimum Distance Between BST Nodes
Problem Description
Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.
Example 1:
Output: 1
Example 2:
Output: 1
Constraints:
- The number of nodes in the tree is in the range
[2, 100]. - 0 <= Node.val <= 105
Solve it on LeetCode
Approaches
1. Brute Force with Inorder Traversal
Intuition:
A binary search tree (BST) has the property that for any node, the value of all the nodes in its left subtree are less and all the nodes in its right subtree are greater. Thus, an inorder traversal of a BST will yield the nodes in sorted order.
The brute force approach is to perform an inorder traversal of the BST to obtain a sorted list of node values. We then compute the minimum difference between consecutive values in this sorted list.
Steps:
- Perform an inorder traversal to extract values in sorted order.
- Calculate the minimum difference between consecutive elements in this sorted list.
Code:
- Time Complexity: O(N) where N is the number of nodes in the tree. We visit each node exactly once.
- Space Complexity: O(N) for the auxiliary space used to store the values of nodes.
2. Optimized Inorder Traversal
Intuition:
We can optimize the space usage by calculating the minimum difference on-the-fly during the inorder traversal, rather than maintaining a list of values. This way, we only need to keep track of the last visited node's value.
Steps:
- Perform an inorder traversal.
- During traversal, calculate the difference between the current node value and the previous node value (i.e., last node visited in inorder traversal).
- Update the minimum difference accordingly.
Code:
- Time Complexity: O(N) where N is the number of nodes. Still, we visit each node exactly once.
- Space Complexity: O(H) where H is the height of the tree. This accounts for the recursion stack during the depth-first traversal which, in the worst case, is the height of the tree.