Within the realm of binary trees, one of the most common problems is to find the largest Binary Search Tree contained within it. In this article, we will learn how to find the largest BST in a binary tree using different approaches. Before that, let's revise the basics.
What are Binary Search Trees?
A Binary Search Tree is a specialized type of binary tree in which the value of each node is greater than all values in its left subtree and smaller than all values in its right subtree. The left and right subtrees of a BST are also BSTs themselves, making it a recursive data structure.
Let's consider the following binary tree as an illustrated example:
In this binary tree, we will find the largest Binary Search Tree (BST) present.
 Starting from the root (10), we recursively traverse the left and right subtrees.
 We check if each subtree is a BST or not by comparing the values of each node with the minimum and maximum values of its respective subtrees.
 At node 15, we compare its value with the minimum and maximum values of its left subtree (12) and right subtree (20). Since 15 is greater than 12 and less than 20, this subtree is a valid BST.
 At node 8, we compare its value with the minimum and maximum values of its right subtree (5). Since 8 is greater than 5, this subtree is also a valid BST.
 At node 5, we compare its value with the minimum and maximum values of its right subtree (9). Since 5 is less than 9, this subtree is not a valid BST.
 As the subtree rooted at 5 is not a valid BST, we discard it.
 Finally, we have identified the largest BST in the binary tree. It is the subtree rooted at node 15, with the following structure:
This subtree has a size of 3 and contains the nodes 12, 15, and 20, satisfying the properties of a BST.
The illustrated example demonstrates the process of finding the largest BST within a binary tree. By comparing the values of each subtree with the minimum and maximum values, we determine the validity of the subtree as a BST. The largest BST identified in the binary tree can provide valuable insights into its structure and hierarchical relationships.
Find the Largest BST in the Binary Tree
To find the largest Binary Search Tree (BST) in a binary tree, we will use DepthFirst Traversal. Starting from the root of the binary tree, we perform a recursive traversal of both the left and right subtrees.
At each node, we compare its value with the minimum and maximum values of its left and right subtrees, ensuring that it satisfies the BST property. If a node violates the BST property, we discard the entire subtree rooted at that node and move to the next node.
Here's a stepbystep algorithm for finding the largest Binary Search Tree (BST) in a binary tree:

Define a class or structure to represent a BST node, containing the following attributes:
 Value: the value of the node.
 Left: a reference to the left child node.
 Right: a reference to the right child node.

Define a class or structure to store the information about the largest BST found, containing the following attributes:
 Size: the number of nodes in the BST.
 MinValue: the minimum value in the BST.
 MaxValue: the maximum value in the BST.
 Root: a reference to the root node of the BST.

Create a function called
largestBST
that takes a binary tree's root node as input and returns the information about the largest BST found. 
Inside the
largestBST
function, implement a recursive helper function calledfindLargestBST
with the following parameters:node
: the current node being processed.minValue
: the minimum value that the subtree rooted atnode
can have.maxValue
: the maximum value that the subtree rooted atnode
can have.

If
node
is null, return information about an empty BST (size = 0, minValue = +∞, maxValue = ∞, root = null). 
Recursively call
findLargestBST
for the left and right child nodes ofnode
. 
Compare the values returned by the left and right subtrees to determine the size, minValue, maxValue, and root of the BST rooted at
node
. There are three cases to consider: a. If both left and right subtrees are BSTs and the value ofnode
is greater than the maximum value of the left subtree and less than the minimum value of the right subtree, then the subtree rooted atnode
is a BST. b. If either the left or right subtree is not a BST, or the value ofnode
is not within the valid range, then the subtree rooted atnode
is not a BST. c. If the subtree rooted atnode
is a BST, update the information about the largest BST found so far if its size is greater than the current largest BST. 
Return the information about the largest BST found among the left and right subtrees of
node
. 
Finally, call the
largestBST
function with the root of the binary tree as the input, and retrieve the information about the largest BST found.
This algorithm employs a recursive approach to traverse the binary tree and evaluate each subtree, identifying the largest BST based on the properties of a BST.
C++ Implementation
Let's take a look at the implementation of the code for finding the largest BST in a binary tree in C++:
#include <iostream> #include <climits> // Structure for a BST node struct Node { int data; Node* left; Node* right; }; // Structure to store information about a BST struct BSTInfo { int size; int minValue; int maxValue; Node* root; }; // Helper function to create a new node Node* createNode(int data) { Node* newNode = new Node(); newNode>data = data; newNode>left = newNode>right = nullptr; return newNode; } // Helper function to check if a binary tree is a BST bool isBSTUtil(Node* node, int minValue, int maxValue) { if (node == nullptr) return true; if (node>data < minValue  node>data > maxValue) return false; return (isBSTUtil(node>left, minValue, node>data  1) && isBSTUtil(node>right, node>data + 1, maxValue)); } // Main function to find the largest BST in a binary tree BSTInfo largestBSTUtil(Node* node) { if (node == nullptr) return {0, INT_MAX, INT_MIN, nullptr}; // Check if the current subtree is a BST if (isBSTUtil(node, INT_MIN, INT_MAX)) return {1, node>data, node>data, node}; // Recursively find the largest BST in the left and right subtrees BSTInfo leftBST = largestBSTUtil(node>left); BSTInfo rightBST = largestBSTUtil(node>right); // Determine the largest BST among the left and right subtrees if (leftBST.size > rightBST.size) return leftBST; else return rightBST; } // Wrapper function to find the largest BST in a binary tree BSTInfo largestBST(Node* root) { return largestBSTUtil(root); } // Test the code with an example binary tree int main() { Node* root = createNode(50); root>left = createNode(30); root>right = createNode(60); root>left>left = createNode(5); root>left>right = createNode(20); root>right>left = createNode(45); root>right>right = createNode(70); root>right>right>left = createNode(65); root>right>right>right = createNode(80); BSTInfo largestBSTInfo = largestBST(root); std::cout << "Size of the largest BST: " << largestBSTInfo.size << std::endl; // Printing the values of the largest BST std::cout << "Largest BST values: "; if (largestBSTInfo.root != nullptr) { std::cout << largestBSTInfo.root>data << " "; std::cout << largestBSTInfo.root>left>data << " "; std::cout << largestBSTInfo.root>right>data << " "; } std::cout << std::endl; return 0; }
Output:
Size of the largest BST: 1 Largest BST values: 60 45 70
The tree we constructed is:
The largest subtree in a binary tree:
This code defines the necessary structures for a binary tree node and stores information about the largest BST found. It includes helper functions to create a new node and check if a binary tree is a BST. The main function largestBST
is a wrapper that calls the largestBSTUtil
function recursively to find the largest BST in the given binary tree.
Time and space Complexity
The time complexity of the code is O(n), where n is the number of nodes in the binary tree. This is because the code performs a depthfirst traversal of the binary tree, visiting each node exactly once. The 'isBSTUtil' function also has a time complexity of O(n) since it checks if the subtree rooted at a node is a BST by traversing the subtree once.
The space complexity of the code is O(h), where h is the height of the binary tree.
Conclusion
You now have the code to find the largest BST in the binary tree with its time and space complexities. Learn more about BST with examples here.