714214. Minimum BST Sum Subtree
Hard
Minimum BST Sum Subtree
Summary
Given a Binary Search Tree (BST), find the minimum sum subtree, where each node is considered as its value. A subtree is considered smaller if its sum is smaller.
Detailed Explanation
To solve this problem, we can follow a recursive approach. The idea is to consider each node in the tree and calculate the sum of all its subtrees. We then compare these sums with the current minimum sum found so far.
Here's a step-by-step breakdown of the solution:
- Traverse the BST in an in-order manner (Left-Root-Right) to visit all nodes.
- For each node, calculate the sum of its left subtree and right subtree recursively.
- Compare this sum with the current minimum sum found so far. If the new sum is smaller, update the minimum sum.
- Repeat steps 1-3 for all nodes in the tree.
Here's an ASCII art diagram illustrating the problem:
5
/ \
2 8
/ \ / \
1 3 6 9
The minimum sum subtree is [1, 2, 3], with a sum of 6.
Time complexity: O(n), where n is the number of nodes in the tree. This is because we visit each node once.
Space complexity: O(h), where h is the height of the tree. This is because of the recursive function calls.
Optimized Solutions
Java
class Node {
int val;
Node left, right;
public Node(int val) {
this.val = val;
left = null;
right = null;
}
}
public class Main {
static int minSum = Integer.MAX_VALUE;
public static void main(String[] args) {
Node root = new Node(5);
root.left = new Node(2);
root.right = new Node(8);
root.left.left = new Node(1);
root.left.right = new Node(3);
root.right.left = new Node(6);
root.right.right = new Node(9);
findMinSum(root);
System.out.println("Minimum sum subtree: " + minSum);
}
public static void findMinSum(Node node) {
if (node == null) return;
int leftSum = 0;
if (node.left != null) {
leftSum = findMinSum(node.left);
}
int rightSum = 0;
if (node.right != null) {
rightSum = findMinSum(node.right);
}
int sum = node.val + leftSum + rightSum;
if (sum < minSum) {
minSum = sum;
}
}
}