Difficulty: Easy | Acceptance: 61.30% | Paid: No Topics: Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Binary Tree
Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.
Examples
Example 1:
Input: root = [4,2,6,1,3]
Output: 1
Explanation:
The minimum difference is 1, which is the difference between node 2 and node 3 (or node 3 and node 2).
Example 2:
Input: root = [1,0,48,null,null,12,49]
Output: 1
Explanation:
The minimum difference is 1, which is the difference between node 48 and node 49 (or node 49 and node 48).
Constraints
The number of nodes in the tree is in the range [2, 100].
0 <= Node.val <= 10^5
Table of Contents
- Examples
- Constraints
- In-order Traversal with Array
- In-order Traversal with Previous Node
- Iterative In-order Traversal
- Morris Traversal
In-order Traversal with Array
Intuition In a BST, an in-order traversal produces values in sorted order. The minimum difference between any two nodes must be between adjacent elements in this sorted sequence.
Steps
- Perform in-order traversal to collect all node values in an array
- Iterate through the array to find the minimum difference between adjacent elements
- Return the minimum difference found
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
values = []
def inorder(node):
if not node:
return
inorder(node.left)
values.append(node.val)
inorder(node.right)
inorder(root)
min_diff = float('inf')
for i in range(1, len(values)):
min_diff = min(min_diff, values[i] - values[i - 1])
return min_diffComplexity
- Time: O(n) where n is the number of nodes
- Space: O(n) for storing all values in the array
- Notes: Simple and intuitive, but uses extra space for the array
In-order Traversal with Previous Node
Intuition Instead of storing all values, we can track the previous node during in-order traversal and calculate the difference on the fly, reducing space complexity.
Steps
- Initialize a variable to track the previous node value
- Perform in-order traversal
- At each node, calculate the difference with the previous node and update the minimum
- Update the previous node to the current node
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
self.min_diff = float('inf')
self.prev = None
def inorder(node):
if not node:
return
inorder(node.left)
if self.prev is not None:
self.min_diff = min(self.min_diff, node.val - self.prev)
self.prev = node.val
inorder(node.right)
inorder(root)
return self.min_diffComplexity
- Time: O(n) where n is the number of nodes
- Space: O(h) where h is the height of the tree (recursion stack)
- Notes: Optimal space complexity for recursive approach
Iterative In-order Traversal
Intuition Use an explicit stack to perform in-order traversal iteratively, avoiding recursion stack overhead.
Steps
- Initialize a stack and current pointer to root
- While stack is not empty or current is not null:
- Push all left children to stack
- Pop a node, process it (calculate difference with previous)
- Move to right child
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
stack = []
curr = root
prev = None
min_diff = float('inf')
while stack or curr:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
if prev is not None:
min_diff = min(min_diff, curr.val - prev)
prev = curr.val
curr = curr.right
return min_diffComplexity
- Time: O(n) where n is the number of nodes
- Space: O(h) where h is the height of the tree (stack space)
- Notes: Avoids recursion, useful for very deep trees
Morris Traversal
Intuition Morris traversal allows in-order traversal with O(1) extra space by temporarily modifying the tree structure.
Steps
- Initialize current pointer to root
- While current is not null:
- If current has no left child, process current and move to right
- Otherwise, find the rightmost node in the left subtree
- If this node’s right is null, make it point to current and move left
- If it already points to current, restore the tree, process current, and move right
python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def minDiffInBST(self, root: Optional[TreeNode]) -> int:
curr = root
prev = None
min_diff = float('inf')
while curr:
if not curr.left:
if prev is not None:
min_diff = min(min_diff, curr.val - prev)
prev = curr.val
curr = curr.right
else:
# Find the rightmost node in left subtree
pre = curr.left
while pre.right and pre.right != curr:
pre = pre.right
if not pre.right:
pre.right = curr
curr = curr.left
else:
pre.right = None
if prev is not None:
min_diff = min(min_diff, curr.val - prev)
prev = curr.val
curr = curr.right
return min_diffComplexity
- Time: O(n) where n is the number of nodes
- Space: O(1) extra space (modifies tree temporarily)
- Notes: Most space-efficient but modifies tree structure during traversal