714247. BST Maximum Difference
BST Maximum Difference
Summary
Given a Binary Search Tree (BST), find the maximum difference between the values of two nodes in the tree. The BST is defined as follows: every node has a value, and for each node, all its left child's values are less than the node's value, while all its right child's values are greater than the node's value.
Detailed Explanation
The problem can be solved by performing an In-Order Traversal of the BST. The maximum difference will occur when the largest node in the tree is paired with the smallest node. This pair can be found during the traversal by keeping track of the minimum and maximum values seen so far. The time complexity for this algorithm is O(n), where n is the number of nodes in the tree, since we need to visit each node once.
Here's a step-by-step breakdown:
- Initialize variables to keep track of the minimum and maximum values seen so far:
minValandmaxVal. - Perform an In-Order Traversal of the BST:
- For each node, update
minValif the node's value is smaller than the currentminVal. - Update
maxValif the node's value is larger than the currentmaxVal.
- For each node, update
- The maximum difference between two nodes in the tree is the difference between the current
maxValandminVal.
Time complexity: O(n) Space complexity: O(1)
Optimized Solutions
Java
public class BSTMaximumDifference {
public int maxDifference(Node root) {
if (root == null) return 0;
int minVal = Integer.MAX_VALUE;
int maxVal = Integer.MIN_VALUE;
maxDifferenceHelper(root, ref(minVal), ref(maxVal));
return maxVal - minVal;
}
private void maxDifferenceHelper(Node node, Ref<Integer> minVal, Ref<Integer> maxVal) {
if (node == null) return;
maxDifferenceHelper(node.left, minVal, maxVal);
*minVal = Math.min(*minVal, node.val);
*maxVal = Math.max(*maxVal, node.val);
maxDifferenceHelper(node.right, minVal, maxVal);
}
}