Given a Binary Tree and a positive integer K. The task is to check whether the Balanced BST of size K exists in a given Binary Tree or not. If it exists then print “Yes” else print “No”.
Examples:
Input: K = 4,
Below is the given Tree:
15
/ \
10 26
/ \ / \
5 12 25 40
/ / \
20 35 50
\
60
Output: Yes
Explanation:
Subtree of the given tree with
size k is given below:
40
/ \
35 50
\
60
Input: K = 4,
Below is the given Tree:
18
/
9
/ \
7 10
Output: No
Explanation:
There is no subtree of size K
which forms a balanced BT.
Approach: The idea is to use the Post Order Traversal. The following are the steps for solving the problem:
- Perform a Post Order Traversal on the given tree and check BST condition for each node where the largest value in the left sub-tree should be smaller than the current value and the smaller value in the right subtree should be greater than the current value.
- Then check if the BST is balanced or not that is the absolute difference between left and right sub-tree should be either 0 or 1.
- Then pass values return from the sub-trees to the parent.
- Perform the above steps for all nodes and take the Boolean variable ans which is initially marked false which is used to check whether a balanced BST is present or not.
- If a Balanced BST of size K is found then print “Yes” else print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// A tree nodestruct node { int data; node* left; node* right;};// Structure of temporary variablestruct minMax { bool isBST; bool balanced; int size; int height; int min; int max;};// Function to create the nodenode* createNode(int value){ node* temp = new node(); temp->left = NULL; temp->right = NULL; temp->data = value;}// Utility function to find Balanced// BST of size kminMax findBalancedBstUtil(node* root, int k, bool& ans){ // Base condition if (root == NULL) return { true, true, 0, 0, INT_MAX, INT_MIN }; // Temporary variable minMax temp; // Recursive call for left sub-tree minMax lsTree = findBalancedBstUtil(root->left, k, ans); if (ans == true) return temp; // Recursive call for right sub-tree minMax rsTree = findBalancedBstUtil(root->right, k, ans); if (ans == true) return temp; // Check those conditions which // violated the rules of BST if (!lsTree.isBST || !rsTree.isBST || lsTree.max > root->data || rsTree.min < root->data) { temp.isBST = false; return temp; } // Check whether the Bst is // height balanced or not if (abs(lsTree.height - rsTree.height) == 1 || abs(lsTree.height - rsTree.height) == 0) temp.balanced = true; else temp.balanced = false; // Make the variable true // as sub-tree is BST temp.isBST = true; // Store the size temp.size = 1 + lsTree.size + rsTree.size; // Store the height temp.height = max(lsTree.height, rsTree.height) + 1; // Store the minimum of BST temp.min = root->left != NULL ? lsTree.min : root->data; // Store the maximum of BST temp.max = root->right != NULL ? rsTree.max : root->data; // Condition to check whether the // size of Balanced BST is K or not if (temp.balanced == true && temp.size == k) { ans = true; } // Return the temporary variable // with updated data return temp;}// Function to find the Balanced// BST of size kstring findBalancedBst(node* root, int k){ bool ans = false; // Utility function call findBalancedBstUtil(root, k, ans); return ans == true ? "Yes" : "No";}// Driver Codeint main(){ // Given Binary Tree node* root = createNode(15); root->left = createNode(10); root->right = createNode(26); root->left->left = createNode(5); root->left->right = createNode(12); root->right->left = createNode(25); root->right->left->left = createNode(20); root->right->right = createNode(40); root->right->right->left = createNode(35); root->right->right->right = createNode(50); root->right->right->right->right = createNode(60); int k = 4; // Function Call cout << findBalancedBst(root, k); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{ static boolean ans;// A tree nodestatic class node { int data; node left; node right;};// Structure of temporary variablestatic class minMax { boolean isBST; boolean balanced; int size; int height; int min; int max; public minMax(boolean isBST, boolean balanced, int size, int height, int min, int max) { super(); this.isBST = isBST; this.balanced = balanced; this.size = size; this.height = height; this.min = min; this.max = max; } public minMax() { // TODO Auto-generated constructor stub }};// Function to create the nodestatic node createNode(int value){ node temp = new node(); temp.left = null; temp.right = null; temp.data = value; return temp;}// Utility function to find Balanced// BST of size kstatic minMax findBalancedBstUtil(node root, int k){ // Base condition if (root == null) return new minMax(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE ); // Temporary variable minMax temp = new minMax(); // Recursive call for left sub-tree minMax lsTree = findBalancedBstUtil(root.left, k); if (ans == true) return temp; // Recursive call for right sub-tree minMax rsTree = findBalancedBstUtil(root.right, k); if (ans == true) return temp; // Check those conditions which // violated the rules of BST if (!lsTree.isBST || !rsTree.isBST || lsTree.max > root.data || rsTree.min < root.data) { temp.isBST = false; return temp; } // Check whether the Bst is // height balanced or not if (Math.abs(lsTree.height - rsTree.height) == 1 || Math.abs(lsTree.height - rsTree.height) == 0) temp.balanced = true; else temp.balanced = false; // Make the variable true // as sub-tree is BST temp.isBST = true; // Store the size temp.size = 1 + lsTree.size + rsTree.size; // Store the height temp.height = Math.max(lsTree.height, rsTree.height) + 1; // Store the minimum of BST temp.min = root.left != null ? lsTree.min : root.data; // Store the maximum of BST temp.max = root.right != null ? rsTree.max : root.data; // Condition to check whether the // size of Balanced BST is K or not if (temp.balanced == true && temp.size == k) { ans = true; } // Return the temporary variable // with updated data return temp;}// Function to find the Balanced// BST of size kstatic String findBalancedBst(node root, int k){ ans = false; // Utility function call findBalancedBstUtil(root, k); return ans == true ? "Yes" : "No";}// Driver Codepublic static void main(String[] args){ // Given Binary Tree node root = createNode(15); root.left = createNode(10); root.right = createNode(26); root.left.left = createNode(5); root.left.right = createNode(12); root.right.left = createNode(25); root.right.left.left = createNode(20); root.right.right = createNode(40); root.right.right.left = createNode(35); root.right.right.right = createNode(50); root.right.right.right.right = createNode(60); int k = 4; // Function call System.out.print(findBalancedBst(root, k));}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approachimport sysans = False# A tree nodeclass createNode: def __init__(self, data): self.data = data self.left = None self.right = None# Structure of temporary variableclass newMinMax: def __init__(self, isBST, balanced, size, height, mn, mx): self.isBST = isBST self.balanced = balanced self.size = size self.height = height self.mn = mn self.mx = mx# Utility function to find Balanced# BST of size kdef findBalancedBstUtil(root, k): global ans # Base condition if (root == None): return newMinMax(True, True, 0, 0, sys.maxsize, -sys.maxsize - 1) # Temporary variable temp = newMinMax(True, True, 0, 0, sys.maxsize, -sys.maxsize - 1) # Recursive call for left sub-tree lsTree = findBalancedBstUtil(root.left, k) if (ans == True): return temp # Recursive call for right sub-tree rsTree = findBalancedBstUtil(root.right, k) if (ans == True): return temp # Check those conditions which # violated the rules of BST if (lsTree.isBST == False or rsTree.isBST == False or lsTree.mx > root.data or rsTree.mn < root.data): temp.isBST = False return temp # Check whether the Bst is # height balanced or not if (abs(lsTree.height - rsTree.height) == 1 or abs(lsTree.height - rsTree.height) == 0): temp.balanced = True else: temp.balanced = False # Make the variable true # as sub-tree is BST temp.isBST = True # Store the size temp.size = 1 + lsTree.size + rsTree.size # Store the height temp.height = max(lsTree.height , rsTree.height) + 1 # Store the minimum of BST if root.left != None: temp.mn = lsTree.mn else: temp.mn = root.data # Store the maximum of BST if root.right != None: temp.mx = rsTree.mx else: temp.mx = root.data # Condition to check whether the # size of Balanced BST is K or not if (temp.balanced == True and temp.size == k): ans = True # Return the temporary variable # with updated data return temp# Function to find the Balanced# BST of size kdef findBalancedBst(root, k): global ans # Utility function call findBalancedBstUtil(root, k) if ans == True: return "Yes" else: return "No"# Driver Codeif __name__ == '__main__': # Given Binary Tree root = createNode(15) root.left = createNode(10) root.right = createNode(26) root.left.left = createNode(5) root.left.right = createNode(12) root.right.left = createNode(25) root.right.left.left = createNode(20) root.right.right = createNode(40) root.right.right.left = createNode(35) root.right.right.right = createNode(50) root.right.right.right.right = createNode(60) k = 4 # Function Call print(findBalancedBst(root, k))# This code is contributed by ipg2016107 |
C#
// C# program for the // above approachusing System;class GFG{ static bool ans;// A tree nodepublic class node { public int data; public node left; public node right;};// Structure of temporary // variablepublic class minMax { public bool isBST; public bool balanced; public int size; public int height; public int min; public int max; public minMax(bool isBST, bool balanced, int size, int height, int min, int max) { this.isBST = isBST; this.balanced = balanced; this.size = size; this.height = height; this.min = min; this.max = max; } public minMax() { // TODO Auto-generated constructor stub }};// Function to create the nodestatic node createNode(int value){ node temp = new node(); temp.left = null; temp.right = null; temp.data = value; return temp;}// Utility function to find Balanced// BST of size kstatic minMax findBalancedBstUtil(node root, int k){ // Base condition if (root == null) return new minMax(true, true, 0, 0, int.MaxValue, int.MinValue); // Temporary variable minMax temp = new minMax(); // Recursive call for left sub-tree minMax lsTree = findBalancedBstUtil(root.left, k); if (ans == true) return temp; // Recursive call for right sub-tree minMax rsTree = findBalancedBstUtil(root.right, k); if (ans == true) return temp; // Check those conditions which // violated the rules of BST if (!lsTree.isBST || !rsTree.isBST || lsTree.max > root.data || rsTree.min < root.data) { temp.isBST = false; return temp; } // Check whether the Bst is // height balanced or not if (Math.Abs(lsTree.height - rsTree.height) == 1 || Math.Abs(lsTree.height - rsTree.height) == 0) temp.balanced = true; else temp.balanced = false; // Make the variable true // as sub-tree is BST temp.isBST = true; // Store the size temp.size = 1 + lsTree.size + rsTree.size; // Store the height temp.height = Math.Max(lsTree.height, rsTree.height) + 1; // Store the minimum of BST temp.min = root.left != null ? lsTree.min : root.data; // Store the maximum of BST temp.max = root.right != null ? rsTree.max : root.data; // Condition to check whether the // size of Balanced BST is K or not if (temp.balanced == true && temp.size == k) { ans = true; } // Return the temporary // variable with updated data return temp;}// Function to find the Balanced// BST of size kstatic String findBalancedBst(node root, int k){ ans = false; // Utility function call findBalancedBstUtil(root, k); return ans == true ? "Yes" : "No";}// Driver Codepublic static void Main(String[] args){ // Given Binary Tree node root = createNode(15); root.left = createNode(10); root.right = createNode(26); root.left.left = createNode(5); root.left.right = createNode(12); root.right.left = createNode(25); root.right.left.left = createNode(20); root.right.right = createNode(40); root.right.right.left = createNode(35); root.right.right.right = createNode(50); root.right.right.right.right = createNode(60); int k = 4; // Function call Console.Write(findBalancedBst(root, k));}}// This code is contributed by Princi Singh |
Javascript
<script> // Javascript program for the above approach let ans = false; // A tree Node class node { constructor(value) { this.left = null; this.right = null; this.data = value; } } // Structure of temporary variable class minMax { constructor(isBST, balanced, size, height, min, max) { this.isBST = isBST; this.balanced = balanced; this.size = size; this.height = height; this.min = min; this.max = max; } } // Function to create the node function createNode(value) { let temp = new node(value); return temp; } // Utility function to find Balanced // BST of size k function findBalancedBstUtil(root, k) { // Base condition if (root == null) return new minMax(true, true, 0, 0, Number.MAX_VALUE, Number.MIN_VALUE ); // Temporary variable let temp = new minMax(); // Recursive call for left sub-tree let lsTree = findBalancedBstUtil(root.left, k); if (ans == true) return temp; // Recursive call for right sub-tree let rsTree = findBalancedBstUtil(root.right, k); if (ans == true) return temp; // Check those conditions which // violated the rules of BST if (!lsTree.isBST || !rsTree.isBST || lsTree.max > root.data || rsTree.min < root.data) { temp.isBST = false; return temp; } // Check whether the Bst is // height balanced or not if (Math.abs(lsTree.height - rsTree.height) == 1 || Math.abs(lsTree.height - rsTree.height) == 0) temp.balanced = true; else temp.balanced = false; // Make the variable true // as sub-tree is BST temp.isBST = true; // Store the size temp.size = 1 + lsTree.size + rsTree.size; // Store the height temp.height = Math.max(lsTree.height, rsTree.height) + 1; // Store the minimum of BST temp.min = root.left != null ? lsTree.min : root.data; // Store the maximum of BST temp.max = root.right != null ? rsTree.max : root.data; // Condition to check whether the // size of Balanced BST is K or not if (temp.balanced == true && temp.size == k) { ans = true; } // Return the temporary variable // with updated data return temp; } // Function to find the Balanced // BST of size k function findBalancedBst(root, k) { ans = false; // Utility function call findBalancedBstUtil(root, k); return ans == true ? "Yes" : "No"; } // Given Binary Tree let root = createNode(15); root.left = createNode(10); root.right = createNode(26); root.left.left = createNode(5); root.left.right = createNode(12); root.right.left = createNode(25); root.right.left.left = createNode(20); root.right.right = createNode(40); root.right.right.left = createNode(35); root.right.right.right = createNode(50); root.right.right.right.right = createNode(60); let k = 4; // Function call document.write(findBalancedBst(root, k)); // This code is contributed by mukesh07.</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
