Given a binary tree and a target, find the number of nodes in the minimum sub-tree with the given sum equal to the target which is also a binary search tree.
Examples:
Input:
13
/ \
5 23
/ \ / \
N 17 N N
/
16
Target: 38
Output: 3
Explanation: 5, 17, 16 is the smallest subtree with length 3.Input:
7
/ \
N 23
/ \
10 23
/ \ / \
N 17 N N
Target: 73
Output: -1
Explanation: No subtree is bst for the given target.
Approach: The problem can be solved using the below idea:
This problem can be solved using Dynamic Programming on Trees.
Below are the steps for the above approach:
- Create a Hashtable to store the subtree, sum of node values in a subtree, minimum value in the subtree, and maximum value in a subtree.
- Initialize the ans as infinity or the maximum possible value.
- Now recursively check for the given tree and its subtrees if it is BST or not.
- In each recursive call, save the value of the sum of nodes for each subtree, the subtree node count(subtree length) for every subtree, the minimum value of the subtree, the maximum value of the subtree.
- If the given subtree is a BST and the sum of nodes of the subtree is equal to the given target update the ans as the minimum of the number of nodes in this subtree or subtree length and previous answer value.
- return true if the given subtree is a BST else return false.
- In the end, the answer will contain the minimum number of nodes in a subtree for a given target or it will be infinity if no answer exists for a given binary tree.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>using namespace std;class Node {public: int data; Node *left, *right; Node(int x) { this->data = x; this->left = 0; this->right = 0; }};class Solution { unordered_map<Node *, int> subTreeLength, sum, mnE, mxE; int minLength = INT_MAX; int target;public: int minSubtreeSumBST(int target, Node* root) { this->target = target; isBST(root); return minLength == INT_MAX ? -1 : minLength; } int isBST(Node* root) { if (root == 0) return 1; int l = isBST(root->left); int r = isBST(root->right); sum[root] = root->data + sum[root->left] + sum[root->right]; mnE[root] = root->left ? mnE[root->left] : root->data; mxE[root] = root->right ? mxE[root->right] : root->data; subTreeLength[root] = 1 + subTreeLength[root->left] + subTreeLength[root->right]; if ((root->left ? mxE[root->left] < root->data : 1) and (root->right ? mnE[root->right] > root->data : 1) and l and r) { if (target == sum[root]) minLength = min(minLength, subTreeLength[root]); return 1; } return 0; }};// Drivers codeint main(){ int target = 38; Node* root = new Node(13); root->left = new Node(5); root->right = new Node(23); root->left->right = new Node(17); root->left->right->left = new Node(16); Solution obj; // Function Call cout << obj.minSubtreeSumBST(target, root); return 0;} |
Java
// JAVA code for the above approach:import java.util.HashMap;class Node { int data; Node left, right; Node(int x) { this.data = x; this.left = null; this.right = null; }}class Solution { // HashMaps to store information for each node HashMap<Node, Integer> subTreeLength, sum, mnE, mxE; int minLength = Integer.MAX_VALUE; int target; int minSubtreeSumBST(int target, Node root) { this.target = target; subTreeLength = new HashMap<>(); sum = new HashMap<>(); mnE = new HashMap<>(); mxE = new HashMap<>(); isBST(root); return minLength == Integer.MAX_VALUE ? -1 : minLength; } int isBST(Node root) { // Base case: empty node if (root == null) return 1; // Recursively check if left and right subtrees are BSTs int l = isBST(root.left); int r = isBST(root.right); // Calculate sum, minimum, and maximum values for the current node sum.put(root, root.data + sum.getOrDefault(root.left, 0) + sum.getOrDefault(root.right, 0)); mnE.put(root, root.left != null ? mnE.get(root.left) : root.data); mxE.put(root, root.right != null ? mxE.get(root.right) : root.data); subTreeLength.put(root, 1 + subTreeLength.getOrDefault(root.left, 0) + subTreeLength.getOrDefault(root.right, 0)); // Check if the current node forms a valid BST subtree with the given properties if ((root.left != null ? mxE.get(root.left) < root.data : true) && (root.right != null ? mnE.get(root.right) > root.data : true) && l != 0 && r != 0) { // If the subtree sum matches the target, update the minimum length if necessary if (target == sum.get(root)) minLength = Math.min(minLength, subTreeLength.get(root)); return 1; } return 0; }}public class Main { public static void main(String[] args) { // Test case int target = 38; Node root = new Node(13); root.left = new Node(5); root.right = new Node(23); root.left.right = new Node(17); root.left.right.left = new Node(16); Solution obj = new Solution(); // Function call to find the minimum subtree sum BST length int result = obj.minSubtreeSumBST(target, root); System.out.println("Minimum subtree sum BST length: " + result); }}// This code is contributed by shivamgupta310570 |
Javascript
class Node { constructor(x) { this.data = x; this.left = null; this.right = null; }}// Define a class for the solution to // find the minimum subtree sum BSTclass GFG { constructor() { // Maps to store various properties of each node this.subTreeLength = new Map(); this.sum = new Map(); this.mnE = new Map(); this.mxE = new Map(); this.minLength = Infinity; this.target = 0; } // Method to find the minimum subtree sum BST minSubtreeSumBST(target, root) { this.target = target; this.isBST(root); return this.minLength === Infinity ? -1 : this.minLength; } // Helper method to traverse the tree and // find the minimum subtree sum BST isBST(root) { if (!root) { return 1; } const l = this.isBST(root.left); const r = this.isBST(root.right); // Calculate properties of the current node this.sum.set(root, root.data + (this.sum.get(root.left) || 0) + (this.sum.get(root.right) || 0)); this.mnE.set(root, root.left ? this.mnE.get(root.left) : root.data); this.mxE.set(root, root.right ? this.mxE.get(root.right) : root.data); this.subTreeLength.set(root, 1 + (this.subTreeLength.get(root.left) || 0) + (this.subTreeLength.get(root.right) || 0)); // Check if the current node's subtree forms a valid BST if ( (!root.left || this.mxE.get(root.left) < root.data) && (!root.right || this.mnE.get(root.right) > root.data) && l && r ) { if (this.target === this.sum.get(root)) { this.minLength = Math.min(this.minLength, this.subTreeLength.get(root)); } return 1; } return 0; }}// Driver codefunction main() { const target = 38; const root = new Node(13); root.left = new Node(5); root.right = new Node(23); root.left.right = new Node(17); root.left.right.left = new Node(16); const obj = new GFG(); // Call the method to find the minimum subtree sum BST and // log the result console.log(obj.minSubtreeSumBST(target, root));}main(); |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
