Closest Pair in a Search Tree

Easy

You are given the root root of a binary search tree: for every node, all values in its left subtree are smaller than its own value and all values in its right subtree are larger. All values are distinct. Return the smallest difference between the values of any two different nodes in the tree.

Example 1

root=tree_node([20, 10, 30, 5, 14, 25]) → 4

In increasing order the values are 5, 10, 14, 20, 25, 30. Neighbouring gaps are 5, 4, 6, 5, 5, so the smallest is 4, between 10 and 14.

Example 2

root=tree_node([50, None, 51]) → 1

There are only two nodes, and they differ by 1.

Constraints

The tree has between 2 and 5 · 10⁴ nodes
0 ≤ Node.val ≤ 10⁵
The tree is a valid binary search tree

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Binary Search Tree Binary Tree

Similar problems

Pair Sum in a Search Tree Easy Identical Trees Easy Mirror-Image Tree Easy Tree Height Easy Nearest Leaf Depth Easy

Input

root=tree_node([20, 10, 30, 5, 14, 25])

Expected

Run checks the first 3 tests in your browser. Submit checks all 52 tests on the server, hidden ones included.