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:
[2, 104].0 <= Node.val <= 105
Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/
In this approach, we will perform an in-order traversal of the BST using an explicit stack to store the node values in a sorted manner. As we traverse the tree, we will calculate the minimum difference between consecutive values.
The C solution uses an iterative approach with a stack to perform an in-order traversal. The stack mimics the call stack used in recursion, storing nodes to revisit them in the correct order. The minimum difference is updated whenever a valid consecutive pair is found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of nodes. Each node is visited exactly once.
Space Complexity: O(H), where H is the height of the tree, representing the maximum size of the stack.
This approach relies on a recursive in-order traversal of the BST to compute the minimum absolute difference. We maintain a global variable to track the smallest difference encountered during traversal.
The C solution implements recursive in-order traversal with helper function inOrder. It retains global variables for previous node value and minimum difference, updating them through recursive traversal.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N)
Space Complexity: O(H), due to recursive call stack.
| Approach | Complexity |
|---|---|
| In-order Traversal Using Stack | Time Complexity: O(N), where N is the number of nodes. Each node is visited exactly once. |
| Recursive In-order Traversal | Time Complexity: O(N) |
Minimum Distance between BST Nodes - Leetcode 783 - Python • NeetCodeIO • 22,987 views views
Watch 9 more video solutions →Practice Minimum Absolute Difference in BST with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor