Check if binary tree contains a balanced BST of size k

Shreya Deep
Last Updated: May 13, 2022

Introduction

Binary Tree is a Data Structure having a root node and at most two children nodes. Each of these children forms the left subtree and the right subtree. The end nodes or the leaf nodes have no children and are pointed by a NULL pointer. 

BST is a type of tree data structure where for every node, all the nodes to the left of this node have a value lesser than the current node’s value, and all the nodes to the right of this node have a value greater than the current node’s value along with the fact that both left subtree and right subtree are also Binary Search Trees. 

 

 

balanced BST is a BST in which the difference between the height of the left and right subtree is either 0 or 1. 

In this article, we’ll learn how to check if a binary tree contains a balanced BST of size k.

Problem Statement

Given a binary tree, check if it contains at least one balanced BST of size k. If it contains, print yes, otherwise no. K is a positive integer and is also given in the input. 

Note: By size k, it means there should be k nodes in the BST.

 

For example

Input

K =3

Output

Yes

 

Explanation

Yes, the tree here is itself a BST. We can find a BST of size three here, which is the left subtree of the root and is also balanced. 

Solution Approach

We will try to build the BST here from the bottom to the top. Thus, the approach will use post-order traversal of the given tree. 

First, we keep the variable “found” equal to 0. This variable will be 0 if we don't find any balanced BST of size k yet, otherwise 1. 

For each node, we will check if it follows the properties of a node of BST or not, i.e., if the value at this node is greater than the maximum value in its left subtree and smaller than the minimum value in its right subtree

Then, once we’re sure if the node follows BST properties, we need to check if it forms a balanced BST, i.e., if the height difference between its left and right subtree is 0/1 or not. If yes, we will then see the size of this balanced BST. If it is equal to k, we have found what we needed and thus update the value of “found” to 1

A few things to notice that we need here are:

  • For checking if a tree is BST, we need to know if its children form a BST or not. If a tree is BST, its children will also be BST. 
     
  • Similarly, for checking if a node follows the BST property, we need to know the maximum value in its left subtree and the minimum value in its right subtree
     
  • Also, to check if a tree is balanced, we need to know the height of its left and right subtree. We also need to know if its left and right subtrees are themselves balanced or not.
     
  • For finding out the size of a BST, we need to know the size of its left and right subtree. Then we add 1 to the sum of the left and right subtree sizes to get the tree size. 
     

Therefore, for each node, we need to store six pieces of information: 

  • if the tree from this node is a BST
     
  • if the tree from this node is a balanced BST
     
  • the minimum value of the left subtree of the tree
     
  • the maximum value of the right subtree of the tree
     
  • the size of the tree from this node and the height of the tree from this node

 

Once we’re done with checking these for all nodes in a post-order traversal way, in the end, we will check the value of found. If it is 1, print yes. Otherwise, no. 

The steps of implementation are:

  • Declare and initialize a variable found to 0.
     
  • Call the function check, which does the post-order traversal and checks all the above-written things for a node. Call this function for the root first.
     
  • In the check function:
     
    • First, write the base condition. If the root is null, it is BST, and it is balanced. Its size is 0, and its height is 0. Also, since there is no node, the maximum value of the left subtree of this root will be INT_MAX, and the minimum value of the right subtree will be INT_MIN.
       
    • Declare a variable, curr of type info for storing info for the current node.
       
    • As in the post-order traversal, we first visit the left subtree, call the function check for the left subtree of the root.
       
    • If we already foundbalanced BST of size k in the left subtree itself, we don't need to move further, so return curr.
       
    • In the post-order traversal, after the left subtree, we go to the right subtree, so call the function check for the right subtree of the root.
       
    • If we already found balanced BST of size k in the right subtree itself, we don't need to move further, so just return curr.
       
    • Now, since the left and the right subtrees don't contain a balanced BST of size k, we have to look for the tree in which the current node is present. 
       
    • So, for the current node to be a part of BST, we check if its left subtree and right subtree is a BST or not. And if the data at the current node satisfies the BST property or not. If it doesn't, update the isBST value for this node as false and return curr.
       
    • If it is valid, update the value of isBST to true.
       
    • If the node is following the BST property, check if it is height-balanced or not. If it is, update the value of isbalanced to true, otherwise false.
       
    • Update the value of size and height of the tree.
       
    • Update the values of minimum and maximum of the tree.
       
    • If the root→left is NULL, the minimum will be the root data itself. Otherwise, the minimum will be the minimum of the left subtree.
       
    • If the root→right is NULL, the maximum will be the root data itself. Otherwise, the maximum will be the maximum of the right subtree.
       
    • Now, if the tree is balanced and its size is k, update the value of found to 1.
       
    • Return curr.
       
  • In the end, if the value of found==1, print “YES”. Otherwise, “NO”.

Java implementation

Below is the JAVA implementation of the above-discussed approach.

// Java program for the above approach
import java.util.*;

class GFG{
	
static boolean ans;

// A tree node
static class node
{
	int data;
	node left;
	node right;
};

// Structure of temporary variable
static 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 node
static 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 k
static 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 k
static String findBalancedBst(node root,
							int k)
{
	ans = false;

	// Utility function call
	findBalancedBstUtil(root, k);
	return ans == true ? "Yes" : "No";
}

// Driver Code
public 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

Output

YES

C++ implementation

Below is the C++ implementation of the above-discussed approach.

#include<bits/stdc++.h>
using namespace std;
template <typename T>
class BinaryTreeNode{ // Class for BinaryTreeNode
   public:
   T data; // Data of the node
   BinaryTreeNode* left; // Left of the node
   BinaryTreeNode* right; // Right of the node
   BinaryTreeNode(T data){  // Constructor for assigning the data to the current node
       this->data=data;
       left=NULL;
       right=NULL;
   }
};
// struct for information needed for finding if the tree is BST of size k
struct info {
   bool isBST; // isBST tells if the tree is a BST
   bool isbalanced; // isbalanced tells if the tree is balanced or not
   int size; // size tells the size of the tree
   int height; // height tells the height of the tree
   int minimum; // minimum tells the minimum number present in the tree
   int maximum; // maximum tells the maximum number present in the tree
};
info check(BinaryTreeNode<int> *root,int k, int& found){
   // Base condition
   if (root == NULL){ 
       // if the root is null, it is BST and it is balanced. Its size is 0
       // and its height is 0. Also, since there is no node, the maximum value 
       // of the left subtree of this root will be INT_MAX and minimum val of 
       // right subtree will be INT_MIN.
       return { true, true, 0, 0, INT_MAX, INT_MIN };
   }

   // Declare a variable of type info for storing info for the current node
   info curr;

   // As in the post-order traversal, we first visit the left subtree,
   // call the check function for the left subtree of the root.
   info left_subtree = check(root->left,k, found);
   // If we already found a balanced BST of size k in the left subtree itself, 
   //we don't need to move further, so just return curr
   if (found == true){
       return curr;
   }

   //In the post-order traversal, after the left subtree, we go to the right 
   //subtree, so, call the check function for the right subtree of the root.
   info right_subtree = check(root->right,k, found);
   //If we already found a balanced BST of size k in the right subtree itself, 
   //we don't need to move further, so just return curr
   if (found == true){
       return curr;
   }
   //Now, since the left and the right subtrees don't contain a balanced 
   //BST of size k, we have to look for the tree in which the current node is
   //present. So, for the current node, to be a part of BST, we check if its
   //left subtree and right subtree is a BST or not. And if the data at the 
   //current node satisfies the BST property or not. If it doesn't,
   //update the isBST value for this node as false and return curr.
   if (!left_subtree.isBST || !right_subtree.isBST || left_subtree.maximum > root->data || right_subtree.minimum < root->data) {
       curr.isBST = false;
       return curr;
   }
   
   //If it is valid, update the value of isBST to true.
   curr.isBST = true;
   //If the node is following the BST property, check if it is height balanced
   // or not. If it is, update the value of isbalanced to true, otherwise false.
   if (abs(left_subtree.height - right_subtree.height) == 1 || abs(left_subtree.height - right_subtree.height) == 0)
       curr.isbalanced = true;
   else
       curr.isbalanced = false;

   // Update the value of size and height of the tree
   curr.size = 1 + left_subtree.size + right_subtree.size;
   curr.height = max(left_subtree.height, right_subtree.height) + 1;

   // Update the values of minimum and maximum of the tree
   //If the root left is NULL, the minimum will be the root data itself,
   //Otherwise, minimum will be the minimum of the left subtree
   curr.minimum = root->left != NULL ? left_subtree.minimum : root->data;

   //If the root right is NULL, the maximum will be the root data itself,
   //Otherwise, maximum will be the maximum of the right subtree
   curr.maximum = root->right != NULL? right_subtree.maximum: root->data;
   // Now, if the tree is balanced and its size is k, update the value of
   // found to 1.
   if (curr.isbalanced == true && curr.size == k) {
       found = 1;
   }
   //Return curr
   return curr;
}
bool func(BinaryTreeNode<int> *root, int k)
{
   int found = 0;
   // Call the function check 
   check(root,k,found);
   if(found==1){
       return true;
   }
   else{
       return false;
   }
}

int main()
{
    
   // Construct a Binary Tree
   BinaryTreeNode<int> *root = NULL;
   root = new BinaryTreeNode<int>(4);
   root->left = new BinaryTreeNode<int>(2);
   root->right = new BinaryTreeNode<int>(5);
   root->left->left = new BinaryTreeNode<int>(1);
   root->left->right = new BinaryTreeNode<int>(3);
   root->right->right = new BinaryTreeNode<int>(6);
   
   int k = 3;
   // Function Call
   if (func(root,k))
       cout << "YES"<<endl;
   else
       cout << "NO"<<endl;
}

Output

YES

Python Implementation

Below is the python implementation of the above-discussed approach.

import sys


ans = False


# This will create a new node.
class createNode:

def __init__(self, data):

self.data = data
self.left = None
self.right = None


# Temporary Varable blueprint.
class 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


# function to find balanced BST of Size 'k'.
def findBalancedBstUtil(root, k):

global ans

# Base case.
if (root == None):
return newMinMax(True, True, 0, 0,
sys.maxsize,
-sys.maxsize - 1)


# Now, we will create a temporary variable.
temp = newMinMax(True, True, 0, 0,
sys.maxsize,
-sys.maxsize - 1)


# Calling recursion on left sub-tree.
lsTree = findBalancedBstUtil(root.left, k)


if (ans == True):
return temp


# Calling recursion on right sub-tree.
rsTree = findBalancedBstUtil(root.right, k)


if (ans == True):
return temp


# Checking Conditions.
if (lsTree.isBST == False or
rsTree.isBST == False or
lsTree.mx > root.data or
rsTree.mn < root.data):
temp.isBST = False
return temp


# Check if its 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


# As subtree is a BST, make isBST true.
temp.isBST = True


# Size.
temp.size = 1 + lsTree.size + rsTree.size


# Height
temp.height = max(lsTree.height ,
rsTree.height) + 1


# Minimum in a BST.
if root.left != None:
temp.mn = lsTree.mn
else:
temp.mn = root.data


# Maximum in a BST.
if root.right != None:
temp.mx = rsTree.mx
else:
temp.mx = root.data


# Checking if size is K or not.
if (temp.balanced == True and
temp.size == k):
ans = True


# Return 
return temp


# This function will find balanced BST
def findBalancedBst(root, k):

global ans

findBalancedBstUtil(root, k)
if ans == True:
return "Yes"
else:
return "No"


# Driver Code
if __name__ == '__main__':

# Creating the 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


# Calling function.
print(findBalancedBst(root, k))


Output

YES

Complexities

Time complexity

O(n), where n is the number of nodes in the tree.

Reason: Here, we’re traversing the tree once in post-order traversal, which requires O(n) time. All other operations require O(1) time. Thus, the overall complexity is O(n).

Space complexity

O(1)

Reason: Only constant extra space is used in the solution by variables. Thus, the space complexity is O(1). 

Frequently asked questions

  1. What is a binary tree?
    A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child.
     
  2. What is a binary tree used for?
    In computing, binary trees are mainly used for searching and sorting as they provide a means to store data hierarchically.
     
  3. What is post-order traversal?
    Post-order traversal is a traversal in which we travel to the left subtree of the node first, then to the right subtree, and then the node itself.
     
  4. What are binary search trees?
    Binary search trees are trees in which, for each node, the value of the node is larger than the maximum value in its left node and smaller than the minimum value in its right subtree.
     
  5. What is the difference between a binary tree and a binary search tree?
    In a binary tree, the children's order doesn't matter, while in a binary search tree, the left child's value should be strictly less than the parent's value and the right child's value should be strictly less than the parent's value.

Key Takeaways

In this article, we have extensively discussed the problem ‘Check if binary tree contains a balanced BST of size k’. We hope that this blog has helped you enhance your knowledge of ‘Check if binary tree contains a balanced BST of size k’ and if you would like to learn more, check out our articles on Library. Do upvote our blog to help other ninjas grow. Happy Coding!”

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think