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:
Input: root = [4,2,6,1,3] Output: 1
Example 2:
Input: root = [1,0,48,null,null,12,49] Output: 1
Constraints:
[2, 100].0 <= Node.val <= 105
Note: This question is the same as 530: https://leetcode.com/problems/minimum-absolute-difference-in-bst/
An inorder traversal of a BST yields nodes in non-decreasing order. By performing an inorder traversal, we can collect the values of the nodes in a sorted manner and then iterate through these values to find the minimum difference between successive nodes.
This solution performs an inorder traversal of the tree. We keep track of the previous node value and calculate the difference between the current node and the previous node. We update the minimum difference accordingly.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N), where N is the number of nodes in the tree since we visit each node exactly once.
Space Complexity: O(H) due to the recursion stack, where H is the height of the tree.
The Morris Traversal is an inorder tree traversal technique that uses constant space by reusing the tree structure. It involves temporarily rearranging the tree to allow traversal without explicit stack use.
In Morris Traversal, we create temporary links between a node and its inorder predecessor to traverse without recursion or stack. This algorithm processes each node in O(1) additional space without altering the tree structure long-term.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N) where each edge is traversed at most twice, once down and once up.
Space Complexity: O(1) because it does not use stack or recursion.
| Approach | Complexity |
|---|---|
| Approach 1: Inorder Traversal | Time Complexity: O(N), where N is the number of nodes in the tree since we visit each node exactly once. Space Complexity: O(H) due to the recursion stack, where H is the height of the tree. |
| Approach 2: Morris Traversal | Time Complexity: O(N) where each edge is traversed at most twice, once down and once up. Space Complexity: O(1) because it does not use stack or recursion. |
Minimum Distance between BST Nodes - Leetcode 783 - Python • NeetCodeIO • 22,987 views views
Watch 9 more video solutions →Practice Minimum Distance Between BST Nodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor