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/
Problem Overview: Given the root of a Binary Search Tree (BST), compute the minimum absolute difference between values of any two different nodes. Because of the BST property, an inorder traversal visits nodes in sorted order, which makes it easy to compare adjacent values.
Approach 1: Inorder Traversal (O(n) time, O(h) space)
The key BST property: inorder traversal returns values in ascending order. Instead of comparing every pair of nodes, you only compare each node with the previously visited node during traversal. Keep a variable prev to store the previous value and update the minimum difference using current - prev. Traverse the tree using DFS recursion or an explicit stack. This reduces the problem from pairwise comparisons to a single pass over the sorted sequence of values.
This approach uses a standard Depth-First Search traversal on a Binary Search Tree. The time complexity is O(n) because each node is visited once. Space complexity is O(h), where h is the tree height, due to the recursion stack (O(log n) for balanced trees, O(n) for skewed trees).
Approach 2: Morris Traversal (O(n) time, O(1) space)
Morris Traversal performs inorder traversal without recursion or a stack by temporarily modifying tree pointers. For each node, locate its inorder predecessor (the rightmost node in its left subtree). Create a temporary thread pointing back to the current node so the traversal can return after finishing the left subtree.
While visiting nodes in inorder order, maintain the same prev value and update the minimum difference exactly as in the standard traversal. After processing, restore the tree structure by removing the temporary threads. This approach keeps the O(n) time complexity but reduces auxiliary space to O(1).
Morris traversal is useful when memory constraints matter or when recursion depth could become large. The logic is more complex than the standard DFS approach but eliminates the stack entirely while still leveraging the sorted order property of a Tree that satisfies BST ordering.
Recommended for interviews: The inorder traversal solution is what interviewers typically expect. It directly uses the BST property and is easy to implement with DFS. Mentioning Morris traversal shows deeper understanding of tree traversal techniques and space optimization, but most interviewers prioritize the clear O(n) DFS solution first.
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.
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.
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.
The problem requires us to find the minimum difference between the values of any two nodes. Since the inorder traversal of a binary search tree is an increasing sequence, we only need to find the minimum difference between the values of two adjacent nodes in the inorder traversal.
We can use a recursive method to implement the inorder traversal. During the process, we use a variable pre to save the value of the previous node. This way, we can calculate the minimum difference between the values of two adjacent nodes during the traversal.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary search tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| 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. |
| Inorder Traversal | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Inorder Traversal (DFS) | O(n) | O(h) | Best general solution. Simple, readable, and expected in most coding interviews. |
| Morris Traversal | O(n) | O(1) | Useful when recursion or stack space must be avoided. More complex but memory efficient. |
Minimum Distance between BST Nodes - Leetcode 783 - Python • NeetCodeIO • 27,325 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