Minimum Absolute Difference in BST
Easy · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Search Tree · Binary Tree
Problem
You are given the root of a binary search tree with distinct values: every value in a node's left subtree is smaller than the node's, and every value in its right subtree is larger.
Return the smallest absolute difference between the values of any two different nodes.
The two closest values need not be parent and child: they can sit in different subtrees.
Examples
Input: root = [8,3,10,1,6,null,14] Output: 2
In sorted order the values are 1, 3, 6, 8, 10, 14. Three pairs differ by 2: 1 and 3, 6 and 8, 8 and 10.
Input: root = [20,5,40,null,18,22,null] Output: 2
18 (in the left subtree) and 20 (the root) differ by 2; so do 20 and 22.
Input: root = [5,null,9] Output: 4
Only one pair.
Constraints
- 2 <= number of nodes <= 10^4
- 0 <= Node.val <= 10^5
- the values are distinct
Approaches
- Collect the values and sort them — time O(n log n), space O(n)
Follow-up
LeetCode 783 asks the same question. With the tree given only as its preorder list, sorting recovers the inorder: the use cases ask for the smallest and the largest gap between sorted neighbours that way.
Related problems
Start free on Cariara · Coding problems · System design studio
