Practice/Meta/Leetcode 530. Minimum Absolute Difference in BST

Leetcode 530. Minimum Absolute Difference in BST

CodingMust

Problem

You are given the root node of a binary search tree (BST). Your task is to determine the smallest absolute 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 its left subtree are smaller than the node's value, and all values in its right subtree are greater than the node's value.

Requirements

1. Calculate the minimum absolute difference between any two different node values
2. The tree contains at least 2 nodes
3. All node values are unique integers
4. Leverage the BST property for an efficient solution

Constraints

• The number of nodes in the tree is in the range [2, 10^4]
• 0 <= Node.val <= 10^5
• Time complexity should be O(n) where n is the number of nodes
• Space complexity should be O(h) where h is the height of the tree (recursion stack)

Examples

Example 1:

` Input: root = [4,2,6,1,3] Tree structure: 4 /
2 6 /
1 3

Output: 1 Explanation: The minimum difference is 1, occurring between pairs like (1,2), (2,3), or (3,4) `

Example 2:

` Input: root = [1,0,48,null,null,12,49] Tree structure: 1 /
0 48 /
12 49

Output: 1 Explanation: The minimum difference is 1, between nodes 48 and 49 `

Example 3:

` Input: root = [5,3,7] Tree structure: 5 /
3 7

Output: 2 Explanation: Both differences (5-3=2 and 7-5=2) equal 2 `