Minimum Distance Between BST Nodes

Minimum Distance Between BST Nodes

1. What is this problem about?

The Minimum Distance Between BST Nodes problem asks for the minimum absolute difference between the values of any two distinct nodes in a Binary Search Tree (BST). Because it's a BST, the values are organized in a specific way that makes finding close values easier than in a general tree.

2. Why is this asked in interviews?

Companies like Meta and Amazon ask this "Easy" question to verify a candidate's understanding of BST properties. The Minimum Distance Between BST Nodes interview question specifically tests whether you know that an in-order traversal of a BST yields values in sorted order. If you know this, the problem reduces to finding the minimum difference between adjacent elements in a sorted list.

3. Algorithmic pattern used

The pattern is In-order Traversal (DFS).

1. Perform an in-order traversal of the BST.
2. Keep track of the previously visited node's value.
3. For the current node, calculate $|current.val - prev.val|$.
4. Update the global minimum difference.
5. Update prev to the current node. This "Binary Search Tree, Tree, DFS interview pattern" is highly efficient, running in $O(N)$ time and $O(H)$ space, where $H$ is the height of the tree.

4. Example explanation

BST: 4 /
2 6 /
1 3

• In-order traversal: [1, 2, 3, 4, 6].
• Differences between adjacent elements:
  • $|2-1| = 1$
  • $|3-2| = 1$
  • $|4-3| = 1$
  • $|6-4| = 2$ Minimum distance is 1.

5. Common mistakes candidates make

In the Minimum Distance Between BST Nodes coding problem, a common mistake is trying to compare every node with every other node, which is $O(N^2)$. Another mistake is only comparing a parent with its immediate children; the closest value to a node might be its in-order predecessor or successor located elsewhere in the tree. Some candidates also forget to handle the first node in the traversal, where there is no prev value to compare against.

6. Interview preparation tip

Always remember the "BST = Sorted Array" rule. Most BST problems become trivial once you apply an in-order traversal. This "BST properties interview pattern" is one of the most frequently tested concepts in tree-based coding questions. Practice doing the traversal iteratively as well as recursively to show depth in your understanding.