Smallest Value Gap in Binary Search Tree

EASY10 pts

You are given the root of a Binary Search Tree (BST). Your task is to compute and return the smallest difference between the values of any two distinct nodes in the tree.

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

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

The difference is calculated as the absolute value of the subtraction between two node values. You need to find the minimum such difference across all possible pairs of nodes in the BST.

Example

Input

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

Output

1

Explanation

The tree has nodes with values 1, 2, 3, 4, 6. When we examine all pairs, the smallest difference occurs between adjacent values in sorted order: |2-1| = 1, |3-2| = 1, |4-3| = 1, |6-4| = 2. Therefore, the minimum difference is 1.

Example

Input

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

Output

1

Explanation

The tree has nodes with values 0, 1, 12, 48, 49. The differences between adjacent sorted values are: |1-0| = 1, |12-1| = 11, |48-12| = 36, |49-48| = 1. The minimum difference is 1, which occurs between nodes 0 and 1, as well as between nodes 48 and 49.

Example

Input

root = [5,3]

Output

2

Explanation

The tree has only two nodes with values 3 and 5. The only possible difference is |5-3| = 2.

Accepted0/0·0% Acceptance

Constraints

The tree contains at least 2 nodes and at most 100 nodes.
0 ≤ Node.val ≤ 10⁵
All node values in the BST are unique.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

root =

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

Loading problem...

Smallest Value Gap in Binary Search Tree (Easy) — Practice with Code Visualizer | OneNoughtOne

Smallest Value Gap in Binary Search Tree

Hints

Smallest Value Gap in Binary Search Tree

Hints