The problem
In a binary search tree, find the smallest difference between any two values.
Input: [4, 2, 6, 1, 3] Output: 1
Picture it
Picture prices sorted on a shelf. An inorder walk of a search tree visits values in sorted order, and the closest pair must be neighbours in that order. So compare each value with the previous one.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
Inorder traversal tracking the previous value. O(n).
Python solution
def get_minimum_difference(root):
prev, best = None, inf
def inorder(node):
nonlocal prev, best
if not node:
return
inorder(node.left)
if prev is not None:
best = min(best, node.val - prev)
prev = node.val
inorder(node.right)
inorder(root)
return bestLeetCode adds the imports for you. To run this on your own machine, put this at the top: from math import inf
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.