Hey, Ninja! Did you know a binary tree is one of the most widely used data structures for storing and organizing data? A balanced binary search tree (BST) is a special binary tree that follows certain rules to ensure optimal performance when searching for elements. With their unique property of maintaining a balanced height, BSTs allow faster search, insert, and delete operations.
In this article, we'll discuss a problem that involves determining if a binary tree contains a balanced BST of size k. Through this article, you will understand the concept of binary trees, balanced BSTs, and 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 you find one, print yes; otherwise, print no. “k” is a positive integer and is given in the input.
Note: Size k means there should be k nodes in the BST.
Sample Example
Consider the following binary tree:
Input: k = 3.
Output: Yes
Explanation:
The tree here is itself a BST. We can find a BST of size three here, which is the left subtree of the root. It is also balanced.
Now that we understand the problem let's move further to learn about its solution. But before that, we'll review some concepts we will use to solve this problem.
Let us build on the momentum with a brief discussion about binary trees.
Binary Tree
It is a hierarchical data structure consisting of nodes and edges, where each node has at most two children. The two children of a node are referred to as its left and right children. The node at the top of the binary tree is commonly known as the root. The nodes with no children are called leaves. To learn more, follow this article
Now, let’s see what’s a binary search tree.
Binary Search Tree
Binary search trees are based on the binary tree data structure and store data in a way that allows for fast search, insertion, and deletion operations. In a BST, each node has at most two child nodes, the left child and the right child. For any node in the tree, all elements in its left subtree are lesser than the node's key, and all elements in its right subtree are greater than the node's key.
In the given problem, we are supposed to look for a balanced binary tree. Let’s see what a balanced binary search tree is, exactly.
Balanced Binary Search Tree
A balanced binary search tree is a type of binary search tree. In this, the heights of the left and right subtrees of every node differ by no more than one. The height of a binary tree is nothing but the number of edges from the root node to the farthest leaf.
Balanced binary search trees have several advantages over unbalanced ones. For example, they ensure that search, insert, and delete operations have a guaranteed time complexity of O(log n), where n indicates the number of nodes in the tree. This makes balanced binary search trees ideal for applications that require fast access to data.
Now, to find the triplet with a given sum, we first need to access each node of the BST. For this, you need to know about tree traversals. Let us discuss them briefly.
Tree Traversal
Tree traversal refers to visiting all the nodes in a tree data structure in a specific order. Consider the following BST to visualize the tree traversals we will discuss further.
There are three common ways to traverse a BST:
In-order traversal: In an in-order traversal of a BST, we visit the nodes in the order of increasing values. First, we explore the left subtree, after that, the root node, and at last, the right subtree. The result of an in-order traversal of a BST will be a sequence of its elements sorted in ascending order.
An in-order traversal of the BST in the example is:
Pre-order traversal: In a pre-order traversal of a BST, we visit the root node first, followed by the nodes in the left subtree, and then the nodes in the right subtree.
Pre-order traversal of the BST in the example is:
Post-order traversal: In a post-order traversal of a BST, we visit the nodes in the reverse order of a pre-order traversal. First, we explore the nodes in the left subtree, after that, the nodes in the right subtree, and finally, the root node.
Post-order traversal of the BST in the example is:
All these traversal methods visit the nodes in a different order, but they all allow us to process every node in the BST.
Now think about which of these traversals will be best suited for our question here.
You’re right; the post-order traversal will be most suited for this problem because we will try to go through the tree from bottom to top. By reading this article, you can learn how to do post-order traversal on a BST.
Now that our basics are brushed-up. Let's learn about the approach we’ll use to solve this problem.
Solution Approach
We will use the following approach to find a balanced BST of size k.
Use post-order traversal to visit each node in the tree.
At each node, check if the value of the node follows the properties of a binary search tree, i.e., if the value of the node is greater than the maximum value in its left subtree and lesser than the minimum value in its right subtree.
If the node follows the properties of a binary search tree, then check if the height difference between its left and right subtree is 0 or 1. If the height difference is 0 or 1, then the node is part of a balanced BST.
The height of a tree can be calculated recursively by finding the maximum height of its left and right subtrees and adding 1 to it. The height of an empty tree is 0.
Check the size of the balanced BST rooted at the current node. If the size equals k, we have found a balanced BST of size k.
Repeat the process for all nodes in the tree.
Let’s now look at the algorithm to code this approach.
Algorithm
Following is the algorithm we will use to check if the binary tree contains a BST of size k.
Define a class SubtreeData to store information about a subtree. The class contains the following attributes:
validBST: Boolean flag indicating if the subtree is a valid BST or not.
validBalancedTree: Boolean flag indicating if the subtree is balanced or not.
treeSize: Integer value indicating the size of the subtree.
treeHeight: Integer value indicating the height of the subtree.
minVal: Integer value indicating the minimum value in the subtree.
maxVal: Integer value indicating the maximum value in the subtree.
Define a helper function helperFunctionBalancedBST to find a balanced BST of size k rooted at 'root.' The function takes three arguments:
root: Pointer to the root node of the subtree being checked.
k: Integer value indicating the size of the balanced BST being searched for.
found: Boolean flag indicating if a balanced BST of size k has been found or not.
The helper function has the following base case:
If the root is Null, return a SubtreeData object representing an empty subtree. In this case, a SubtreeData object is returned with values of validBST(true), validBalancedTree(true), treeSize(0), treeHeight (0), minVal(INT_MIN), and maxVal (INT_MAX).
Recursively check the left and right subtrees using the helper function, storing their SubtreeData objects in leftSubtree and rightSubtree, respectively.
If a balanced BST of size k has already been found, return an empty SubtreeData object.
Check if the current subtree is a valid BST by verifying that both the left and right subtrees are valid BSTs and that the minimum and maximum values of the left and right subtrees do not violate the ordering of the root node.
If the subtree is not a valid BST, return a SubtreeData object with values indicating an invalid BST.
In this case, a SubtreeData object is returned with values of validBST(false), validBalancedTree(false), treeSize(0), treeHeight (0), minVal(0), and maxVal (0).
Check if the current subtree is a balanced tree by verifying that the absolute difference between the heights of the left and right subtrees is at most 1. Store the boolean result in the variable validBalancedTree.
Compute the SubtreeData object for the current subtree by setting its values based on the values of the left and right subtrees and the root node.
Set the validBST value to true. This is because we have already dealt with the case of an invalid BST. If we reach here, the subtree is a valid BST.
The value of validBalancedTree value to the value computed in step 7.
The treeSize value to 1 plus the sizes of the left and right subtrees.
The treeHeight value to 1 plus the maximum height of the left and right subtrees.
The minVal to the minimum value of the left subtree or the value of the root node if there is no left subtree.
The maxVal to the maximum value of the right subtree or the value of the root node if there is no right subtree.
The current subtree is a balanced BST of size k if the treeSize = k and validBalancedTree = True. In this case, set the found variable to true.
Return the SubtreeData object for the current subtree.
Define a function check that takes in a TreeNode pointer 'root' and an integer 'k,' representing the desired size of the balanced BST.
In the check function, set the found variable to false and call the helper function helperFunctionBalancedBST with the parameters 'root', 'k,' and 'found.'
If a balanced BST of size k was found, return 1; otherwise, return 0.
If the check function returns true, print, "Balanced BST of size k exists." Otherwise, print, " Balanced BST of size k doesn’t exist."
Let us now look at the implementation of this algorithm.
Implementation
Following is the implementation of the above-discussed approach in Java, C++, and Python.
Implementation in Java
import java.util.*;
// A binary tree node
class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
// Class to store information about a subtree
class SubtreeData {
boolean validBST;
boolean validBalancedTree;
int treeSize;
int treeHeight;
int minVal;
int maxVal;
public SubtreeData(boolean validBST, boolean validBalancedTree, int treeSize, int treeHeight, int minVal, int maxVal) {
this.validBST = validBST;
this.validBalancedTree = validBalancedTree;
this.treeSize = treeSize;
this.treeHeight = treeHeight;
this.minVal = minVal;
this.maxVal = maxVal;
}
}
public class Main {
// Function to create a tree node
static TreeNode makeTree(int value) {
TreeNode temp = new TreeNode();
temp.left = temp.right = null;
temp.val = value;
return temp;
}
/*
Helper function to find
a balanced BST of treeSize k. It
returns information about the
subtree rooted at 'root'
*/
static SubtreeData helperFunctionBalancedBST(TreeNode root, int k, boolean[] found) {
// Base case: empty subtree
if (root == null) {
return new SubtreeData(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
/*
Recursively check the
left and right subtrees
*/
SubtreeData leftSubtree = helperFunctionBalancedBST(root.left, k, found);
if (found[0]) {
return new SubtreeData(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
SubtreeData rightSubtree = helperFunctionBalancedBST(root.right, k, found);
if (found[0]) {
return new SubtreeData(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
}
/*
Check if the current
subtree is a valid BST
*/
if (!leftSubtree.validBST || !rightSubtree.validBST ||
(root.left != null && leftSubtree.maxVal > root.val) ||
(root.right != null && rightSubtree.minVal < root.val)) {
return new SubtreeData(false, false, 0, 0, 0, 0);
}
/*
Check if the current
subtree is balanced
*/
boolean validBalancedTree = (Math.abs(leftSubtree.treeHeight - rightSubtree.treeHeight) <= 1);
// Compute the information for the current subtree
SubtreeData currentSubtree = new SubtreeData(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
currentSubtree.validBST = true;
currentSubtree.validBalancedTree = validBalancedTree;
currentSubtree.treeSize = 1 + leftSubtree.treeSize + rightSubtree.treeSize;
currentSubtree.treeHeight = Math.max(leftSubtree.treeHeight, rightSubtree.treeHeight) + 1;
// Finding currentSubtree.minVal
if (root.left != null) {
currentSubtree.minVal = leftSubtree.minVal;
} else {
currentSubtree.minVal = root.val;
}
// Finding currentSubtree.mixVal
if (root.right != null) {
currentSubtree.maxVal = rightSubtree.maxVal;
} else {
currentSubtree.maxVal = root.val;
}
/*
If the current subtree is
a balanced BST of treeSize k,
we're done!
*/
if (validBalancedTree && currentSubtree.treeSize == k) {
found[0] = true;
}
/*
Return the information
for the current subtree
*/
return currentSubtree;
}
/*
Finds a balanced BST of
Size k rooted at 'root'
*/
static int check(TreeNode root, int k) {
boolean[] found = new boolean[1];
SubtreeData result = helperFunctionBalancedBST(root, k, found);
if (found[0]) {
return 1;
} else {
return 0;
}
}
public static void main(String[] args) {
TreeNode root = makeTree(4);
root.left = makeTree(2);
root.right = makeTree(5);
root.left.left = makeTree(1);
root.left.right = makeTree(3);
root.right.right = makeTree(6);
int k = 3;
int balancedBST = check(root, k);
if (balancedBST == 1) {
System.out.println("Balanced BST of size k exists");
} else {
System.out.println("Balanced BST of size k doesn't exist");
}
}
}
Output
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// A binary tree node
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
};
// Structure to store information about a subtree
struct SubtreeData {
bool validBST;
bool validBalancedTree;
int treeSize;
int treeHeight;
int minVal;
int maxVal;
};
// Function to create a tree node
TreeNode* makeTree(int value) {
TreeNode* temp = new TreeNode();
temp->left = temp->right= NULL;
temp->val = value;
return temp;
}
/*
Helper function to find
a balanced BST of treeSize k. It
returns information about the
subtree rooted at 'root'
*/
SubtreeData helperFunctionBalancedBST(TreeNode* root, int k, bool &found) {
// Base case: empty subtree
if (root == NULL) {
return { true, true, 0, 0, INT_MAX, INT_MIN };
}
/*
Recursively check the
left and right subtrees
*/
SubtreeData leftSubtree = helperFunctionBalancedBST(root->left, k, found);
if (found) {
return {};
}
SubtreeData rightSubtree = helperFunctionBalancedBST(root->right, k, found);
if (found) {
return {};
}
/*
Check if the current
subtree is a valid BST
*/
if (!leftSubtree.validBST || !rightSubtree.validBST ||
(root->left != NULL && leftSubtree.maxVal > root->val) ||
(root->right != NULL && rightSubtree.minVal < root->val)) {
return { false, false, 0, 0, 0, 0 };
}
/*
Check if the current
subtree is balanced
*/
bool validBalancedTree = (abs(leftSubtree.treeHeight - rightSubtree.treeHeight) <= 1);
// Compute the information for the current subtree
SubtreeData currentSubtree;
currentSubtree.validBST = true;
currentSubtree.validBalancedTree = validBalancedTree;
currentSubtree.treeSize = 1 + leftSubtree.treeSize + rightSubtree.treeSize;
currentSubtree.treeHeight = max(leftSubtree.treeHeight, rightSubtree.treeHeight) + 1;
// Finding currentSubtree.minVal
if (root->left != NULL) {
currentSubtree.minVal = leftSubtree.minVal;
}
else {
currentSubtree.minVal = root->val;
}
// Finding currentSubtree.mixVal
if (root->right != NULL) {
currentSubtree.maxVal = rightSubtree.maxVal;
}
else {
currentSubtree.maxVal = root->val;
}
/*
If the current subtree is
a balanced BST of treeSize k,
we're done!
*/
if (validBalancedTree && currentSubtree.treeSize == k) {
found = true;
}
/*
Return the information
for the current subtree
*/
return currentSubtree;
}
/*
Finds a balanced BST of
Size k rooted at 'root'
*/
int check(TreeNode* root, int k) {
bool found = false;
SubtreeData result = helperFunctionBalancedBST(root, k, found);
if (found) {
return 1;
}
else {
return 0;
}
}
int main() {
TreeNode * root = makeTree(4);
root -> left = makeTree(2);
root -> right = makeTree(5);
root -> left -> left = makeTree(1);
root -> left -> right = makeTree(3);
root -> right -> right = makeTree(6);
int k = 3;
int balancedBST = check(root, k);
if(balancedBST) {
cout<<"Balanced BST of size k exists"<<endl;
}
else {
cout<<"Balanced BST of size k doesn't exist"<<endl;
}
return 0;
}
Output
Implementation in Python
# Class to store information about a subtree
class SubtreeData:
def __init__(self, validBST, validBalancedTree, treeSize, treeHeight, minVal, maxVal):
self.validBST = validBST
self.validBalancedTree = validBalancedTree
self.treeSize = treeSize
self.treeHeight = treeHeight
self.minVal = minVal
self.maxVal = maxVal
# A binary tree node
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Function to create a tree node
def makeTree(value):
temp = TreeNode()
temp.left = temp.right = None
temp.val = value
return temp
"""
Helper function to find
a balanced BST of treeSize k. It
returns information about the
subtree rooted at 'root'
"""
def helperFunctionBalancedBST(root, k, found):
# Base case: empty subtree
if root is None:
return SubtreeData(True, True, 0, 0, float('inf'), float('-inf'))
# Recursively check the left and right subtrees
leftSubtree = helperFunctionBalancedBST(root.left, k, found)
if found[0]:
return SubtreeData(True, True, 0, 0, float('inf'), float('-inf'))
rightSubtree = helperFunctionBalancedBST(root.right, k, found)
if found[0]:
return SubtreeData(True, True, 0, 0, float('inf'), float('-inf'))
# Check if the current subtree is a valid BST
if not leftSubtree.validBST or not rightSubtree.validBST or \
(root.left and leftSubtree.maxVal > root.val) or \
(root.right and rightSubtree.minVal < root.val):
return SubtreeData(False, False, 0, 0, 0, 0)
# Check if the current subtree is balanced
validBalancedTree = (abs(leftSubtree.treeHeight - rightSubtree.treeHeight) <= 1)
# Compute the information for the current subtree
currentSubtree = SubtreeData(True, True, 0, 0, float('inf'), float('-inf'))
currentSubtree.validBST = True
currentSubtree.validBalancedTree = validBalancedTree
currentSubtree.treeSize = 1 + leftSubtree.treeSize + rightSubtree.treeSize
currentSubtree.treeHeight = max(leftSubtree.treeHeight, rightSubtree.treeHeight) + 1
# Finding currentSubtree.minVal
if root.left is not None:
currentSubtree.minVal = leftSubtree.minVal
else:
currentSubtree.minVal = root.val
# Finding currentSubtree.mixVal
if root.right is not None:
currentSubtree.maxVal = rightSubtree.maxVal
else:
currentSubtree.maxVal = root.val
# If the current subtree is a balanced BST of treeSize k, we're done!
if validBalancedTree and currentSubtree.treeSize == k:
found[0] = True
# Return the information for the current subtree
return currentSubtree
"""
Finds a balanced BST of Size k rooted at 'root'
"""
def check(root, k):
found = [False]
result = helperFunctionBalancedBST(root, k, found)
if found[0]:
return 1
else:
return 0
if __name__ == '__main__':
root = makeTree(4)
root.left = makeTree(2)
root.right = makeTree(5)
root.left.left = makeTree(1)
root.left.right = makeTree(3)
root.right.right = makeTree(6)
k = 3
balanced_bst = check(root, k)
if balanced_bst == 1:
print("Balanced BST of size k exists")
else:
print("Balanced BST of size k doesn't exist")
Output
Complexity Analysis
Following is the time and space complexity analysis of this code.
Time Complexity
O(n) is the time complexity, where n indicates the number of tree nodes.
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(n) is the space complexity, where n is the tree's height.
Reason: The maximum number of function calls that can be made in the stack would equal the tree's height. In the worst case, where the tree is skewed, the height would equal n, so the space complexity would be O(n).
Frequently Asked Questions
What is a binary tree?
A binary tree is a hierarchical data structure in which each node can have not more than two children. These children are referred to as the left child and the right child.
What is a binary tree used for?
The main use of binary trees is in searching and sorting. This is because they provide a means to store data hierarchically.
What are binary search trees?
Binary search trees are trees in which, for each node, the node's value is largerthan the maximum value in its left node and lesserthan the minimum value in its right subtree.
What is tree traversal?
Tree traversal refers to visiting all the nodes in a tree data structure in a specific order.
What is post-order traversal?
Post-order traversal is a traversal in which we travel first to the left subtree of the node, then to the right subtree, and then to the node itself.
Conclusion
In this article, we learned about the solution to a famous problem of “checking if the binary tree has a balanced BST of size K.” We also learned about its implementation in popular programming languages and their complexity analysis.
You can refer to the following articles to learn more about tree data structure.
8+ registered 