DSA · Trees · #121
Minimum Absolute Difference in BST
Module 44 · difficulty 2/5·⏱ 30:00starts on first keystroke
Given the `root` of a Binary Search Tree (BST), return the **minimum absolute difference** between the values of any two different nodes in the tree. Each node holds the shape `{ val, left, right }` with `left`/`right` being `null` when absent. The BST property holds: for every node, all values in its left subtree are smaller and all values in its right subtree are larger. Implement `function getMinimumDifference(root)` returning a number. The tree has at least two nodes.
Examples
root = [4,2,6,1,3]→1— Sorted in-order values are [1,2,3,4,6]; the closest pair (e.g. 1 and 2, or 2 and 3, or 3 and 4) differs by 1.root = [1,0,48,null,null,12,49]→1— Sorted values [0,1,12,48,49]; the closest pair is 48 and 49.root = [5,3]→2— Only two nodes, |5 - 3| = 2.
Constraints
- · The number of nodes is in the range [2, 10^4].
- · 0 <= Node.val <= 10^5
- · The input tree is a valid Binary Search Tree.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.