Find the largest binary search subtree in a given binary tree

In this problem, we are given a binary tree BT. Our task is tofind the largest binary search subtreein 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:

在给定的二叉树中找到最大的二叉搜索子树 - C++中的第1集

Output: 3

Explanation

Full binary tree is a BST.

Copy after login

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 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 "<
        
         Copy after login

Output

The size of the largest possible BST is 5

Copy after login

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 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 "<
        
         Copy after login

Output

The Size of the largest BST is 5

Copy after login

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!