Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hey Ninjas! Many common questions are asked in the companies' interviews and coding rounds. These require knowledge of Data Structures and Algorithms. One of the most common topics for the Interview is knowledge of Binary Trees and Binary Search trees. A common prerequisite for these questions is Recursion.
A common question in the coding interview that checks the knowledge of Binary Trees and Binary Search Trees is the Number of Binary Search Trees present in a Binary Tree.
Problem Statement
A binary tree is provided to us as input. The objective is to count the number of binary search trees (BSTs) that are contained as subtrees in the binary tree. A BST is a binary tree in which the right child is greater than the root and the left child is less.
Sample Example
Let's understand the problem statement better with the help of a sample example given below.
Input:
Output:
Number of BSTs in the Binary Tree is 4.
Explanation:
There are 3 leaf nodes and 1 subtree rooted at 2, which are valid BSTs. Hence our answer is 4.
Approach
Let us first understand what a binary search tree is.
A BST is a binary tree with the following properties:
The root node's value is greater than the maximum value in the left subtree.
The root node's value is smaller than the minimum value in the right subtree.
The above two conditions must hold for every possible subtree. A tree with 0 or 1 node is considered to be a BST. If a tree is a binary search tree, all its subtrees will be binary search trees and vice versa.
The idea to solve this problem is by recursively traversing the tree, checking if each subtree is a BST, and then updating a struct that holds information about the subtree, including the minimum and maximum values in the subtree and the number of BSTs in the subtree.
Algorithm
We'll take a bottom-up approach. Every node will return four pieces of data.
'MINVAL': stores the subtree's lowest value.
'MAXVAL': saves the subtree's maximum value.
'isBST': a boolean (true/false) value determining whether the subtree is a BST.
'numBSTs': stores the total number of valid BSTs.
This information will then be used to build our solution recursively. Every node will make two calls, one to each of its children (left and right, if at all they are present). As previously mentioned, each call will return a chunk of the data mentioned above.
This information will then be used to check the following condition: the left and right subtrees are BST, and the node's value is greater than 'MAXVAL' in the left subtree and less than 'MINVAL' in the right subtree.
If the preceding condition holds, the currently processed subtree is a valid BST; otherwise, it is not. As a result, we will update the variables 'MINVAL,' 'MAXVAL,' 'isBST,' and 'numBSTs' before returning this chunk of data to the caller.
Dry Run
The binary tree's root node (10) is then input into the countBSTs function. The root node is not NULL in this instance. The function repeatedly invokes itself on the root node's left and right subtrees.
The function is called with the left child of the root node as its input on the first recursive call. The left child is valued at 2, while the children to its left and right are valued at 1 and 8, respectively. The left and right subtrees of the left child are then subjected to recursive calls to the countBSTs function. (As both the left and right child are leaf nodes, they are BST), the left and right subtree are both BSTs and the value at the root node is greater than the maximum value in the left subtree. So the total number of BSTs till now is 3(left child of root(10), i.e. 2, leaf nodes 1 and 8).
The right child of the root node (5) is passed as input to the function on the second recursive call. A BST Data Structure with default values is returned by the countBSTs method since the left child does not have any child, so it is a BST.So the total number of BSTs till now is 4(left child of root(10), i.e. 2, leaf nodes 1, 8 and 5).
As the countBSTs function is complete, we get the total number of BSTs present in the binary tree as 4.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// Define a tree node struct with left and right children and a value
struct TreeNode{
int val;
TreeNode *left, *right;
TreeNode(int x){
this->val = x;
this->left = NULL;
this->right = NULL;
}
};
// Define a struct to hold information about the binary search tree
struct BSTdata{
int maxval, minval, numBSTs;
bool isBST;
// Constructor initializes values to default values
BSTdata(){
this->isBST = true;
this->numBSTs = 0;
this->minval = INT_MAX;
this->maxval = INT_MIN;
}
};
// Recursive function to count the number of binary search trees in a given tree
BSTdata countBSTs(TreeNode *root){
// Create a new BSTdata struct to hold information about this subtree
BSTdata newroot = BSTdata();
// If the root is null, return the default values (no BSTs, and min/max values set to infinity and negative infinity respectively)
if (root == NULL){
return newroot;
}
// Recursively count the number of BSTs in the left and right subtrees
BSTdata BSTdataLeft = countBSTs(root->left);
BSTdata BSTdataRight = countBSTs(root->right);
// If both the left and right subtrees are BSTs, and the root value is between the minimum value of the right subtree and the maximum value of the left subtree,
// then this entire subtree is a BST. Update the values of newroot accordingly.
if (BSTdataLeft.isBST and BSTdataRight.isBST and (root->val > BSTdataLeft.maxval and root->val < BSTdataRight.minval)){
newroot.numBSTs = BSTdataLeft.numBSTs + BSTdataRight.numBSTs + 1;
newroot.minval = min(root->val, BSTdataLeft.minval);
newroot.maxval = max(root->val, BSTdataRight.maxval);
}
// Otherwise, this subtree is not a BST. Update the values of newroot accordingly.
else{
newroot.isBST = false;
newroot.numBSTs = BSTdataLeft.numBSTs + BSTdataRight.numBSTs;
newroot.minval = min(root->val, min(BSTdataLeft.minval, BSTdataRight.minval));
newroot.maxval = max(root->val, max(BSTdataLeft.maxval, BSTdataRight.maxval));
}
// Return the newroot BSTdata struct
return newroot;
}
int main(){
// Create a binary tree to test the countBSTs function
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(2);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(8);
root->right = new TreeNode(5);
// Print the number of BSTs in the tree using the countBSTs function
cout << "Number of BST's in given Binary tree is " << countBSTs(root).numBSTs << endl;
}
You can also try this code with Online C++ Compiler
import sys
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class BSTdata:
def __init__(self):
# Initialize minval and maxval with appropriate values
self.maxval = -sys.maxsize-1
self.minval = sys.maxsize
self.numBSTs = 0
self.isBST = True
def countBSTs(root: TreeNode) -> BSTdata:
newroot = BSTdata()
# If root is None, return newroot
if root == None:
return newroot
# Recursively call countBSTs for left and right subtrees
BSTdataLeft = countBSTs(root.left)
BSTdataRight = countBSTs(root.right)
# If both left and right subtrees are BST and root value is greater than max value of left subtree
# and smaller than min value of right subtree, the current tree is also BST
if BSTdataLeft.isBST and BSTdataRight.isBST and root.val > BSTdataLeft.maxval and root.val < BSTdataRight.minval:
newroot.numBSTs = BSTdataLeft.numBSTs + BSTdataRight.numBSTs + 1
newroot.minval = min(root.val, BSTdataLeft.minval)
newroot.maxval = max(root.val, BSTdataRight.maxval)
# Else, current tree is not BST
else:
newroot.isBST = False
newroot.numBSTs = BSTdataLeft.numBSTs + BSTdataRight.numBSTs
newroot.minval = min(root.val, min(BSTdataLeft.minval, BSTdataRight.minval))
newroot.maxval = max(root.val, max(BSTdataLeft.maxval, BSTdataRight.maxval))
# Return the newroot
return newroot
if __name__ == "__main__":
# Create the given binary tree
root = TreeNode(10)
root.left = TreeNode(2)
root.left.left = TreeNode(1)
root.left.right = TreeNode(8)
root.right = TreeNode(5)
# Print the number of BSTs in the given binary tree
print("Number of BST's in given Binary tree is", countBSTs(root).numBSTs)
Output:
Implementation in Java
import java.util.*;
// Define a tree node class with left and right children and a value
class TreeNode {
int val;
TreeNode left, right;
public TreeNode(int x) {
this.val = x;
this.left = null;
this.right = null;
}
}
// Define a class to hold information about the binary search tree
class BSTdata {
int maxval, minval, numBSTs;
boolean isBST;
// Constructor initializes values to default values
public BSTdata() {
this.isBST = true;
this.numBSTs = 0;
this.minval = Integer.MAX_VALUE;
this.maxval = Integer.MIN_VALUE;
}
}
public class Main {
// Recursive function to count the number of binary search trees in a given tree
public static BSTdata countBSTs(TreeNode root) {
// Create a new BSTdata object to hold information about this subtree
BSTdata newroot = new BSTdata();
// If the root is null, return the default values (no BSTs, and min/max values set to infinity and negative infinity respectively)
if (root == null) {
return newroot;
}
// Recursively count the number of BSTs in the left and right subtrees
BSTdata BSTdataLeft = countBSTs(root.left);
BSTdata BSTdataRight = countBSTs(root.right);
// If both the left and right subtrees are BSTs, and the root value is between the minimum value of the right subtree and the maximum value of the left subtree,then this entire subtree is a BST. Update the values of newroot accordingly.
if (BSTdataLeft.isBST && BSTdataRight.isBST && (root.val > BSTdataLeft.maxval && root.val < BSTdataRight.minval)) {
newroot.numBSTs = BSTdataLeft.numBSTs + BSTdataRight.numBSTs + 1;
newroot.minval = Math.min(root.val, BSTdataLeft.minval);
newroot.maxval = Math.max(root.val, BSTdataRight.maxval);
} else {
// Otherwise, this subtree is not a BST. Update the values of newroot accordingly.
newroot.isBST = false;
newroot.numBSTs = BSTdataLeft.numBSTs + BSTdataRight.numBSTs;
newroot.minval = Math.min(root.val, Math.min(BSTdataLeft.minval, BSTdataRight.minval));
newroot.maxval = Math.max(root.val, Math.max(BSTdataLeft.maxval, BSTdataRight.maxval));
}
// Return the newroot BSTdata object
return newroot;
}
public static void main(String[] args) {
// Create a binary tree to test the countBSTs function
TreeNode root = new TreeNode(10);
root.left = new TreeNode(2);
root.left.left = new TreeNode(1);
root.left.right = new TreeNode(8);
root.right = new TreeNode(5);
// Print the number of BSTs in the tree using the countBSTs function
System.out.println("Number of BST's in given Binary tree is " + countBSTs(root).numBSTs);
}
}
Output:
Time Complexity
The time complexity of the function countBSTs is O(n), where n is the number of nodes in the binary tree and represents how many times the function recursively visits each node in the binary tree. The main function merely calls the countBSTs function and initialises the binary tree. Hence its time complexity is O(1). Overall, the time complexity of the given code is O(n).
Space Complexity
The height of the binary tree, which in the worst-case scenario can reach n, determines how much space is consumed by the recursive function call stack. Thus, the countBSTs function's space complexity is O(n). The BSTdata class' newroot object doesn't increase the complexity of the space because its space consumption is constant. The main function does not increase the space complexity because it merely initialises the binary tree and executes the countBSTs method. Overall, the given code has a space complexity O(n).
Frequently Asked Questions
What do you mean by Binary Search Tree?
In a binary search tree, the left subtree of each node only contains nodes whose values are smaller than the node. The only elements in the node's right subtree are those with more than the node's value. Moreover, the left and right subtrees must also be binary search trees.
What is a binary tree?
A binary tree is a tree data structure in which each node can have at most two children, referred to as the left and right child.
How do you traverse a binary tree?
There are three main methods for traversing a binary tree: Inorder traversal: Visit the left, root, and right subtree. Preorder traversal: Visit the root, then the left subtree, then the right subtree. Postorder traversal: Visit the left subtree, right subtree, and root.
What is time complexity?
The time an algorithm or code takes to execute each instruction is known as its time complexity.
What is space complexity?
The total memory space used by an algorithm or code, including the space of input values, is referred to as "space complexity".
Conclusion
This article discusses the topic of Counting the Number of Binary Search Trees in a Binary Tree. In detail, we have seen the problem statement, sample example, algorithm, dry run, and implementation in two languages. Along with this, we also saw the time and space complexity.
We hope this blog has helped you enhance your knowledge of the count of cycles in a connected undirected graph. If you want to learn more, then check out our articles.
But suppose you have just started your learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, you must look at the problems, interview experiences, and interview bundles for placement preparations.
However, you may consider our paid courses to give your career an edge over others!
84+ registered