Minimum Absolute Difference in BST

Easy

Description

Given a binary search tree (BST), find the smallest gap between the values of two different nodes. The gap between two numbers is never negative: it is the bigger one minus the smaller one.

How the judge passes the data

Examples

Example 1:

Input: root = [10,4,15,null,6,12,20]
Output: 2
Explanation: The sorted values are 4, 6, 10, 12, 15, 20. The smallest gap is 2 (for example 4 and 6).

Example 2:

Input: root = [50,30,70,20,40,60,80]
Output: 10
Explanation: The sorted values are 20, 30, 40, 50, 60, 70, 80. Every gap is 10.

Example 3:

Input: root = [9,6,null,5]
Output: 1
Explanation: The sorted values are 5, 6, 9. The smallest gap is 1.

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

Constraints

2 <= Number of nodes <= 10^4
0 <= Node.val <= 10^5

Examples

3 shown

Example 1

Input

[10,4,15,null,6,12,20]

Output

Example 2

Input

[50,30,70,20,40,60,80]

Output

Example 3

Input

[9,6,null,5]

Output

Opening the editor...