Given a binary tree and a target K, the task is to find the diameter of the minimum subtree having sum equal to K which is also a binary search tree. Return -1 if not possible.
Examples:
Input: K = 38
13
/ \
5 23
/ \ / \
N 17 N N
/ \
16 N
Output: 3
Explanation: 5, 17, 16 is the smallest subtree with diameter 3.Input: K = 73
7
/ \
N 23
/ \
10 23
/ \ / \
N 17 N N
Output: -1
Explanation: No subtree is BST for the given target.
Approach:
This problem can be solved using the idea of Dynamic Programming on Trees. Store the sum and diameter of every subtree and check if a subtree with sum K is also a binary search tree or not.
The following steps can be taken to solve this problem:
- Create Hash tables to store the sum of the subtree, diameter of subtree, min value of subtree, and max value of subtree.
- Initialize the answer as infinity.
- Now store all values in the hash tables and check if the given binary tree is a BST using Depth-first traversal.
- During the traversal, only the hash tables will be filled.
- For a binary to be a BST following 3 conditions must be satisfied:
- Left and right subtree must be BST.
- Max value of left subtree < value of the current node
- Min value of right subtree > value of the current node
Below is the implementation of the above approach:
C++
// C++ code to implement this approach#include <bits/stdc++.h>using namespace std;// Structure of node of treestruct Node { int data; Node* left; Node* right; Node(int num) { data = num; left = NULL; right = NULL; }};int target, ans;// Hash Tables to store Minimum value, Maximum Value,// diameter of subtree and sum of elements of subtreeunordered_map<Node *, int> minv, maxv, h, sum;// Function to check if the tree is a BST or notbool isBST(Node* root){ // Base condition if (root == NULL) return true; if (root->left == NULL and root->right == NULL) { minv[root] = root->data; maxv[root] = root->data; h[root] = 1; sum[root] = root->data; if (sum[root] == target) ans = min(ans, h[root]); return true; } // Condition for Binary tree to be a BST if (root->left == NULL) { if (isBST(root->right) and minv[root->right] > root->data) { minv[root] = root->data; maxv[root] = maxv[root->right]; h[root] = h[root->right] + 1; sum[root] = sum[root->right] + root->data; if (sum[root] == target) ans = min(ans, h[root]); return true; } return false; } if (root->right == NULL) { if (isBST(root->left) and maxv[root->left] < root->data) { minv[root] = minv[root->left]; maxv[root] = root->data; h[root] = h[root->left] + 1; sum[root] = sum[root->left] + root->data; if (sum[root] == target) ans = min(ans, h[root]); return true; } return false; } bool bstleft = isBST(root->left); bool bstright = isBST(root->right); if (bstleft and bstright and maxv[root->left] < root->data and minv[root->right] > root->data) { minv[root] = minv[root->left]; maxv[root] = maxv[root->right]; h[root] = 1 + h[root->left] + h[root->right]; sum[root] = root->data + sum[root->left] + sum[root->right]; if (sum[root] == target) ans = min(ans, h[root]); return true; } return false;}// Function to find the desired subtreeint minSubtreeSumBST(int k, Node* root){ // Initialize answer as infinity(INT_MAX) ans = INT_MAX; target = k; // check for BST using DFS traversal isBST(root); if (ans == INT_MAX) return -1; return ans;}// Driver codeint main(){ int k = 38; // Defining tree 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); // Function call int res = minSubtreeSumBST(k, root); cout << res << endl; return 0;} |
Java
// java code for the above approachimport java.util.*;class Node { int data; Node left; Node right; Node(int num) { data = num; left = null; right = null; }}class Main { static int target, ans; // Hash Tables to store Minimum value, Maximum Value, // diameter of subtree and sum of elements of subtree static Map<Node, Integer> minv = new HashMap<>(); static Map<Node, Integer> maxv = new HashMap<>(); static Map<Node, Integer> h = new HashMap<>(); static Map<Node, Integer> sum = new HashMap<>(); // Function to check if the tree is a BST or not public static boolean isBST(Node root) { // Base condition if (root == null) return true; if (root.left == null && root.right == null) { minv.put(root, root.data); maxv.put(root, root.data); h.put(root, 1); sum.put(root, root.data); if (sum.get(root) == target) ans = Math.min(ans, h.get(root)); return true; } // Condition for Binary tree to be a BST if (root.left == null) { if (isBST(root.right) && minv.get(root.right) > root.data) { minv.put(root, root.data); maxv.put(root, maxv.get(root.right)); h.put(root, h.get(root.right) + 1); sum.put(root, sum.get(root.right) + root.data); if (sum.get(root) == target) ans = Math.min(ans, h.get(root)); return true; } return false; } if (root.right == null) { if (isBST(root.left) && maxv.get(root.left) < root.data) { minv.put(root, minv.get(root.left)); maxv.put(root, root.data); h.put(root, h.get(root.left) + 1); sum.put(root, sum.get(root.left) + root.data); if (sum.get(root) == target) ans = Math.min(ans, h.get(root)); return true; } return false; } boolean bstleft = isBST(root.left); boolean bstright = isBST(root.right); if (bstleft && bstright && maxv.get(root.left) < root.data && minv.get(root.right) > root.data) { minv.put(root, minv.get(root.left)); maxv.put(root, maxv.get(root.right)); h.put(root, 1 + h.get(root.left) + h.get(root.right)); sum.put(root, root.data + sum.get(root.left) + sum.get(root.right)); if (sum.get(root) == target) ans = Math.min(ans, h.get(root)); return true; } return false; } // Function to find the desired subtree public static int minSubtreeSumBST(int k, Node root) { // Initialize answer as infinity(INT_MAX) ans = Integer.MAX_VALUE; target = k; // check for BST using DFS traversal isBST(root); if (ans == Integer.MAX_VALUE) return -1; return ans; } // Driver code public static void main(String[] args) { int k = 38; // Defining tree 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); // Function call int res = minSubtreeSumBST(k, root); System.out.println(res); }}// This code is contributed by ik_9 |
Python3
#python code# Structure of node of treeclass Node: def __init__(self, num): self.data = num self.left = None self.right = Nonetarget, ans = None, float('inf')# Hash Tables to store Minimum value, Maximum Value,# diameter of subtree and sum of elements of subtreeminv, maxv, h, sum = {}, {}, {}, {}# Function to check if the tree is a BST or notdef isBST(root): global ans # Base condition if root == None: return True if root.left == None and root.right == None: minv[root] = root.data maxv[root] = root.data h[root] = 1 sum[root] = root.data if sum[root] == target: ans = min(ans, h[root]) return True # Condition for Binary tree to be a BST if root.left == None: if isBST(root.right) and minv[root.right] > root.data: minv[root] = root.data maxv[root] = maxv[root.right] h[root] = h[root.right] + 1 sum[root] = sum[root.right] + root.data if sum[root] == target: ans = min(ans, h[root]) return True return False if root.right == None: if isBST(root.left) and maxv[root.left] < root.data: minv[root] = minv[root.left] maxv[root] = root.data h[root] = h[root.left] + 1 sum[root] = sum[root.left] + root.data if sum[root] == target: ans = min(ans, h[root]) return True return False bstleft = isBST(root.left) bstright = isBST(root.right) if bstleft and bstright and maxv[root.left] < root.data and minv[root.right] > root.data: minv[root] = minv[root.left] maxv[root] = maxv[root.right] h[root] = 1 + h[root.left] + h[root.right] sum[root] = root.data + sum[root.left] + sum[root.right] if sum[root] == target: ans = min(ans, h[root]) return True return False# Function to find the desired subtreedef minSubtreeSumBST(k, root): # Initialize answer as infinity(INT_MAX) global ans, target ans = float('inf') target = k # check for BST using DFS traversal isBST(root) if ans == float('inf'): return -1 return ansk = 38root = Node(13)root.left = Node(5)root.right = Node(23)root.left.right = Node(17)root.left.right.left = Node(16)res = minSubtreeSumBST(k, root)print(res) |
C#
// C# code for the above approachusing System;using System.Collections.Generic;class Node{ public int data; public Node left; public Node right; public Node(int num) { data = num; left = null; right = null; }}class Program{ static int target, ans; // Hash Tables to store Minimum value, Maximum Value, // diameter of subtree and sum of elements of subtree static Dictionary<Node, int> minv = new Dictionary<Node, int>(); static Dictionary<Node, int> maxv = new Dictionary<Node, int>(); static Dictionary<Node, int> h = new Dictionary<Node, int>(); static Dictionary<Node, int> sum = new Dictionary<Node, int>(); // Function to check if the tree is a BST or not public static bool isBST(Node root) { // Base condition if (root == null) return true; if (root.left == null && root.right == null) { minv[root] = root.data; maxv[root] = root.data; h[root] = 1; sum[root] = root.data; if (sum[root] == target) ans = Math.Min(ans, h[root]); return true; } // Condition for Binary tree to be a BST if (root.left == null) { if (isBST(root.right) && minv[root.right] > root.data) { minv[root] = root.data; maxv[root] = maxv[root.right]; h[root] = h[root.right] + 1; sum[root] = sum[root.right] + root.data; if (sum[root] == target) ans = Math.Min(ans, h[root]); return true; } return false; } if (root.right == null) { if (isBST(root.left) && maxv[root.left] < root.data) { minv[root] = minv[root.left]; maxv[root] = root.data; h[root] = h[root.left] + 1; sum[root] = sum[root.left] + root.data; if (sum[root] == target) ans = Math.Min(ans, h[root]); return true; } return false; } bool bstleft = isBST(root.left); bool bstright = isBST(root.right); if (bstleft && bstright && maxv[root.left] < root.data && minv[root.right] > root.data) { minv[root] = minv[root.left]; maxv[root] = maxv[root.right]; h[root] = 1 + h[root.left] + h[root.right]; sum[root] = root.data + sum[root.left] + sum[root.right];if (sum[root] == target)ans = Math.Min(ans, h[root]);return true;}return false;}// Function to find the desired subtreepublic static int minSubtreeSumBST(int k, Node root){ // Initialize answer as infinity(INT_MAX) ans = int.MaxValue; target = k; // check for BST using DFS traversal isBST(root); if (ans == int.MaxValue) return -1; return ans;}// Driver codepublic static void Main(string[] args){ int k = 38; // Defining tree 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); // Function call int res = minSubtreeSumBST(k, root); Console.WriteLine(res);}} |
Javascript
// JavaScript code to implement this approach// tree node structureclass Node{ constructor(num){ this.data = num; this.left = null; this.right = null; }}let target, ans;// Hash Tables to store Minimum value, Maximum Value,// diameter of subtree and sum of elements of subtreelet minv = new Map();let maxv = new Map();let h = new Map();let sum = new Map();// Function to check if the tree is a BST or notfunction isBST(root){ // Base condition if(root == null) return true; if(root.left == null && root.right == null){ minv.set(root, root.data); maxv.set(root, root.data); h.set(root, 1); sum.set(root, root.data); if(sum.get(root) == target){ ans = Math.min(ans, h.get(root)); } return true; } // condition for binary tree to be a BST if(root.left == null){ if(isBST(root.right) && minv.get(root.right) > root.data){ minv.set(root, root.data); maxv.set(root, maxv.get(root.right)); h.set(root, h.get(root.right) + 1); sum.set(root, sum.get(root.right) + root.data); if(sum.get(root) == target){ ans = Math.min(ans, h.get(root)); } return true; } return false; } if(root.right == null){ if(isBST(root.left) && maxv.get(root.left) < root.data){ minv.set(root, minv.get(root.left)); maxv.set(root, root.data); h.set(root, h.get(root.left) + 1); sum.set(root, sum.get(root.left) + root.data); if(sum.get(root) == target){ ans = Math.min(ans, h.get(root)); } return true; } return false; } let bstleft = isBST(root.left); let bstright = isBST(root.right); if(bstleft && bstright && maxv.get(root.left) < root.data && minv.get(root.right) > root.data){ minv.set(root, minv.get(root.left)); maxv.set(root, maxv.get(root.right)); h.set(root, 1 + h.get(root.left) + h.get(root.right)); sum.set(root, root.data + sum.get(root.left) + sum.get(root.right)); if(sum.get(root) == target){ ans = Math.min(ans, h.get(root)); } return true; } return false;}// Function to find the desired subtreefunction minSubtreeSumBST(k, root){ // initialize answer as infinity(INT_MAX) ans = Number.MAX_VALUE; target = k; // check for BST using DFS traversal isBST(root); if(ans == Number.MAX_VALUE){ return -1; } return ans;}// Driver codelet k = 38;// defining treelet 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);// function calllet res = minSubtreeSumBST(k, root);console.log(res);// This code is contributed by Yash Agarwal(yashagarwal2852002) |
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!
