LeetCode 530 · Trees · DFS

Minimum Absolute Difference in BST, explained with a picture

The closest two prices in a sorted tree.

Trees · DFS
▶ Watch it step by step

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 best

LeetCode 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.