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 tree struct 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 subtree unordered_map<Node *, int > minv, maxv, h, sum; // Function to check if the tree is a BST or not bool 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 subtree int 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 code int 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 approach import 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 tree class Node: def __init__( self , num): self .data = num self .left = None self .right = None target, ans = None , float ( 'inf' ) # Hash Tables to store Minimum value, Maximum Value, # diameter of subtree and sum of elements of subtree minv, maxv, h, sum = {}, {}, {}, {} # Function to check if the tree is a BST or not def 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 subtree def 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 ans k = 38 root = 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 approach using 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 subtree public 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 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); Console.WriteLine(res); } } |
Javascript
// JavaScript code to implement this approach // tree node structure class 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 subtree let 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 not function 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 subtree function 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 code let k = 38; // defining tree let 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 let res = minSubtreeSumBST(k, root); console.log(res); // This code is contributed by Yash Agarwal(yashagarwal2852002) |
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!