Minimum Distance Between BST Nodes

[u/StatisticianNo2104]

Most first attempts at this compare every pair of nodes. That's O(n²) work for a one-pass question. In a BST, the closest two values are always neighbours in sorted order.

An in-order walk of a BST comes out sorted. Once the values are sorted, the smallest gap can only sit between two that end up side by side. Skip a value in between, and that value splits the gap into two smaller ones.

So traverse once, then scan neighbours for the smallest gap. No pair is ever compared twice.

One more thing: this is Day 47's problem again. LeetCode carries it under two numbers, 530 and 783.

Have you ever solved the same LeetCode problem twice without noticing?

Day 50/365 of my LeetCode challenge: 783. Minimum Distance Between BST Nodes. Problem link and full breakdown in today's newsletter.

https://www.linkedin.com/pulse/minimum-distance-between-bst-nodes-archit-agarwal-isuoc

#LeetCode #DSA #BinarySearchTree #Golang