# Java O(n) Easy To Read, Optimal Solution

• Explanation
The idea to this question is to use a recursive approach to traverse through the tree, while propagating a Result object that helps us make calculations later on.

Suppose we're considering any given node, n, in getMinimumDifferenceHelper(...).

Firstly, we make recursive calls on n's left and right children. This gives us the propagated min, max, and minimum absolute difference of both left and right subtrees.

Secondly, do we use an existing, propagated minimum absolute difference from the left or right subtree, or can we compute an even smaller value using n's value? We use the fact that n is a BST to see if we can compute an even smaller value involving n's value:

/* To compute absolute difference values involving input n: */

/* Left side absolute difference:  */ root.val - leftResult.max;
/* Right side absolute difference: */ rightResult.min - root.val;

Lastly, we update min, max, minimum absolute difference for n, package it into a Result object and return that.

Time Complexity
The time complexity is O(n) where n is the number of nodes in the tree rooted at input root, since we DFS through the tree to visit each node.

class Solution {

/* Records the min, max values, absDiff within a tree */
class Result {
int min;
int max;
int absDiff; // Minimum absolute difference
Result(int minimum, int maximum, int abs) {
min = minimum;
max = maximum;
absDiff = abs;
}
}

/* Returns a Result object that contains the min, max, minimum absolute
*   diff values within the tree root
*/
public Result getMinimumDifferenceHelper(TreeNode root) {
if (root == null) {
return null;
}
Result leftResult = getMinimumDifferenceHelper(root.left);
Result rightResult = getMinimumDifferenceHelper(root.right);

// Initialize both left and right absolute values absurdly high
int leftSideAbsDiff = Integer.MAX_VALUE;
int rightSideAbsDiff = Integer.MAX_VALUE;

// Compute the absolute difference involving the left subtree
if (leftResult != null) {
leftSideAbsDiff = Math.min(leftResult.absDiff,
root.val - leftResult.max);
}
// Compute the absolute difference involving the right subtree
if (rightResult != null) {
rightSideAbsDiff = Math.min(rightResult.absDiff,
rightResult.min - root.val);
}
// Compute all necessary data to return a new Result
int min = leftResult != null ? leftResult.min : root.val;
int max = rightResult != null ? rightResult.max : root.val;
int absDiff = Math.min(leftSideAbsDiff, rightSideAbsDiff);

return new Result(min, max, absDiff);
}

public int getMinimumDifference(TreeNode root) {
Result result = getMinimumDifferenceHelper(root);
return result.absDiff;
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.