Find the largest binary search subtree in a given binary tree - Episode 1 in C++

In this problem, we are given a binary tree BT. Our task is to find the largest binary search subtree in a given binary tree.

Binary tree is a special data structure used for data storage. Binary trees have a special condition that each node can have at most two child nodes.

Binary search tree (BST) is a tree that satisfies the following properties:

• The key value of the left subtree is smaller than the key value of its parent node (root node) value.

• The key value of the right subtree is greater than or equal to the key value of its parent node (root node).

Let us take an example to understand this problem,

Enter:

Output: 3

Explanation

Full binary tree is a BST.

Solution

The simple way to solve the problem is to perform an in-order traversal of the tree. For each node of the tree, check whether its subtree is a binary search tree. Finally, the size of the largest binary search subtree is returned.

Example

Procedural example illustrating how our solution works

#include<bits/stdc++.h>
using namespace std;
class node{
   public:
   int data;
   node* left;
   node* right;
   node(int data){
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
int findTreeSize(node* node) {
   if (node == NULL)
      return 0;
   else
      return(findTreeSize(node->left) + findTreeSize(node->right) + 1);
}
int isBSTree(struct node* node) {
   if (node == NULL)
      return 1;
   if (node->left != NULL && node->left->data > node->data)
      return 0;
   if (node->right != NULL && node->right->data < node->data)
      return 0;
   if (!isBSTree(node->left) || !isBSTree(node->right))
      return 0;
   return 1;
}
int findlargestBSTSize(struct node *root) {
   if (isBSTree(root)){
      return findTreeSize(root);
}
else
   return max(findlargestBSTSize(root->left), findlargestBSTSize(root->right));
}
int main() {
   node *root = new node(5);
   root->left = new node(2);
   root->right = new node(8);
   root->left->left = new node(1);
   root->left->right = new node(4);
   cout<<"The size of the largest possible BST is "<<findlargestBSTSize(root);
   return 0;
}

Output

The size of the largest possible BST is 5

Another approach

Another way to solve this problem is to traverse the tree from the bottom and check if it is a BST by its child nodes. To do this we will track the following: whether

is BST.

• In the case of the left subtree, the value of the largest element.

• In the case of the right subtree, the value of the smallest element. These values ​​need to be compared with the current node to check the BST.

Additionally, the size of the maximum BST will be updated by comparing it to the size of the current BST.

Example

#include<bits/stdc++.h>
using namespace std;
class node{
   public:
   int data;
   node* left;
   node* right;
   node(int data){
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
int findlargestBSTSizeRec(node* node, int *minValRsubTree, int *maxValLsubTree, int *maxBSTSize, bool *isBSTree) {
   if (node == NULL){
      *isBSTree = true;
      return 0;
   }
   int min = INT_MAX;
   bool left_flag = false;
   bool right_flag = false;
   int leftSubtreeSize,rightSubTreeSize;
   *maxValLsubTree = INT_MIN;
   leftSubtreeSize = findlargestBSTSizeRec(node->left, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
   if (*isBSTree == true && node->data > *maxValLsubTree)
      left_flag = true;
   min = *minValRsubTree;
   *minValRsubTree = INT_MAX;
   rightSubTreeSize = findlargestBSTSizeRec(node->right, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
   if (*isBSTree == true && node->data < *minValRsubTree)
      right_flag = true;
   if (min < *minValRsubTree)
      *minValRsubTree = min;
   if (node->data < *minValRsubTree)
      *minValRsubTree = node->data;
   if (node->data > *maxValLsubTree)
      *maxValLsubTree = node->data;
   if(left_flag && right_flag){
      if (leftSubtreeSize + rightSubTreeSize + 1 > *maxBSTSize)
         *maxBSTSize = (leftSubtreeSize + rightSubTreeSize + 1);
      return (leftSubtreeSize + rightSubTreeSize + 1);
   }
   else{
      *isBSTree = false;
      return 0;
   }
}
int findlargestBSTSize(node* node){
   int min = INT_MAX;
   int max = INT_MIN;
   int largestBSTSize = 0;
   bool isBST = false;
   findlargestBSTSizeRec(node, &min, &max, &largestBSTSize, &isBST);
   return largestBSTSize;
}
int main(){
   node *root = new node(5);
   root->left = new node(2);
   root->right = new node(8);
   root->left->left = new node(1);
   root->left->right = new node(4);
   cout<<"The Size of the largest BST is "<<findlargestBSTSize(root);
   return 0;
}

Output

The Size of the largest BST is 5

The above is the detailed content of Find the largest binary search subtree in a given binary tree - Episode 1 in C++. For more information, please follow other related articles on the PHP Chinese website!