How do you solve Minimum Distance Between BST Nodes on LeetCode?

Minimum Distance Between BST Nodes (LeetCode #783) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: In a BST, in-order traversal yields sorted values.

What is the time complexity of Minimum Distance Between BST Nodes?

The optimal solution for Minimum Distance Between BST Nodes runs in O(n) time and uses O(n) space. The time complexity is O(n) because we traverse each node once, and the space complexity is O(n) due to storing the values in a list.

What is the brute force solution for Minimum Distance Between BST Nodes?

The brute force approach for Minimum Distance Between BST Nodes is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach involves calculating the difference between every pair of nodes in the BST. Since the tree is a binary search tree, we can traverse it and collect all the values, then compare each value with every other value to find the minimum difference. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Minimum Distance Between BST Nodes?

Explain your thought process clearly before coding. Consider edge cases and constraints upfront. Discuss time and space complexities as you develop your solution.

What are common mistakes when solving Minimum Distance Between BST Nodes?

Not using in-order traversal to leverage BST properties. Forgetting to handle edge cases like duplicate values.

#783

Minimum Distance Between BST Nodes

Easy

TreeDepth-First SearchBreadth-First SearchBinary Search TreeBinary TreeIn-order TraversalSortingTwo Pointers

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution takes advantage of the properties of a BST. By performing an in-order traversal, we can ensure that the values are collected in sorted order. This allows us to simply compare adjacent values to find the minimum difference, which is much more efficient.

⚙️

Algorithm

3 steps

1Step 1: Perform an in-order traversal of the BST to collect values in a sorted list.
2Step 2: Initialize a variable to store the minimum difference, set it to a large number.
3Step 3: Iterate through the sorted list and compare each value with the next one to find the minimum difference.

solution.py19 lines

1# Full working Python code
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8def minDiffInBST(root):
9    values = []
10    def inorder(node):
11        if node:
12            inorder(node.left)
13            values.append(node.val)
14            inorder(node.right)
15    inorder(root)
16    min_diff = float('inf')
17    for i in range(1, len(values)):
18        min_diff = min(min_diff, values[i] - values[i - 1])
19    return min_diff

ℹ

Complexity note: The time complexity is O(n) because we traverse each node once, and the space complexity is O(n) due to storing the values in a list.

1In a BST, in-order traversal yields sorted values.
2The minimum difference will always be between adjacent values in the sorted list.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.