Closest Warehouse Bin Codes

A regional distribution warehouse organizes its storage bins in a binary search tree keyed by bin code, so pickers can locate any bin quickly by comparing codes as they descend from the root. Warehouse safety auditors worry that two bins with very close codes could be mixed up during a rushed pick, so they want to know the smallest possible difference between the codes of any two distinct bins in the facility.

You are given the tree's structure as a list of nodes. Each node has a unique integer bin code and, other than leaf nodes, pointers to its left and right child nodes; the ordering of the tree obeys the binary search tree property (every code in a left subtree is smaller than its node's code, and every code in a right subtree is larger). Determine the minimum absolute difference between the bin codes of any two distinct bins in the warehouse.

Input format

• The first line contains a single integer n, the number of bins (nodes) in the tree.
• Each of the next n lines describes one node as four integers id value left right, where id is the node's index (0-indexed), value is its bin code, and left/right are the indices of its left and right child nodes, or -1 if that child does not exist. The node with id = 0 is always the root.

Output format

Print a single integer: the minimum absolute difference between the bin codes of any two distinct bins.

Constraints

• 2 <= n <= 100
• 0 <= value <= 100000
• All bin codes are distinct.
• The described tree is a valid binary search tree containing exactly n nodes, rooted at id 0.

5
0 4 1 2
1 2 3 4
2 6 -1 -1
3 1 -1 -1
4 3 -1 -1

1

3
0 1 -1 1
1 3 2 -1
2 2 -1 -1

1