Closest Value Gap in Search Tree

EASY10 pts

Given the root node of a Binary Search Tree (BST), compute and return the smallest absolute difference between the values of any two distinct nodes in the tree.

A Binary Search Tree is a tree data structure where for every node:

All values in its left subtree are strictly less than the node's value
All values in its right subtree are strictly greater than the node's value

The absolute difference between two values a and b is defined as |a - b|, which equals a - b if a ≥ b, and b - a otherwise.

Your task is to examine all possible pairs of nodes in the tree and find the pair with the minimum absolute difference between their values.

Example

Input

root = [4,2,6,1,3]

Output

1

Explanation

The BST contains nodes with values 1, 2, 3, 4, and 6. When examining all pairs, the minimum absolute differences occur between adjacent values in sorted order: |2-1| = 1, |3-2| = 1, |4-3| = 1. Multiple pairs achieve the minimum value of 1.

Example

Input

root = [1,0,48,null,null,12,49]

Output

1

Explanation

The tree has values 0, 1, 12, 48, and 49. The smallest absolute difference is |1-0| = 1, which is the gap between the two smallest values in the tree.

Example

Input

root = [5,3,8]

Output

2

Explanation

The tree contains only three nodes: 3, 5, and 8. The differences are |5-3| = 2 and |8-5| = 3. Therefore, the minimum absolute difference is 2.

Accepted0/0·0% Acceptance

Constraints

The tree contains at least 2 nodes and at most 10⁴ nodes.
0 ≤ Node.val ≤ 10⁵
The input tree is guaranteed to be a valid Binary Search Tree.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

root =

[5,3,8]

Given the root node of a Binary Search Tree (BST), compute and return the smallest absolute difference between the values of any two distinct nodes in the tree.

A Binary Search Tree is a tree data structure where for every node:

All values in its left subtree are strictly less than the node's value
All values in its right subtree are strictly greater than the node's value

The absolute difference between two values a and b is defined as |a - b|, which equals a - b if a ≥ b, and b - a otherwise.

Your task is to examine all possible pairs of nodes in the tree and find the pair with the minimum absolute difference between their values.

Closest Value Gap in Search Tree

Hints

Closest Value Gap in Search Tree

Hints