Translate Largest BST in a Binary Tree in C++

In a binary tree, each child node has only two nodes (left and right). A tree structure is just a representation of data. A Binary Search Tree (BST) is a special type of binary tree that satisfies these conditions -

• The left child node is smaller compared to its parent

• The parent node of the right child node is larger than the child node

Assuming that given a binary tree, we should find the largest binary search tree (BST).

In this task, we will create a function to find the largest BST in a binary tree. When the binary tree itself is a BST, the size of the entire binary tree can be determined. For example -

Enter

  10
  /\
 5  15
 /\  \
1  8  7

As shown in the figure, the highlighted BST subtree is the largest in this example. '3' is the size of the subtree, so the return value is the size of the subtree.

Input

    52
    / \
   37 67
   /\ / \
 12 27 57 77
          /\
         72 87

Output

5

A subtree whose node length is less than the length of its parent node has a maximum size of three BST node.

Methods to find the largest BST in a given binary tree

For each node x, a binary tree is a BST if the following points are valid. Only nodes with data less than their parent node's data will appear in the node's left subtree. Only one node can have more data than its parent. Both the left subtree and the right subtree should be represented by a binary search tree (BST).

The algorithm will be -

We will do inorder traversal from a binary tree and using recursion. For the current node "ROOT" we will do the following -

• If it is the root of a valid BST, we will return its size.

• Otherwise, we will find the largest BST in the left and right subtrees.

Example

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left;
   struct Node *right;
};
struct Node *
newNode (int data) {
   struct Node *node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
struct Detail {
   int size;
   int max;
   int min;
   int ans;
   bool isBST;
};
bool isBST (Node * root, int min, int max) {
   if (root == NULL) {
      return true;
   }
   if (root->data < min || root->data > max) {
      return false;
   }
   return isBST (root->left, min, root->data - 1) &&
   isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
   if (root == NULL) {
      return 0;
   }
   return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
   // Current Subtree is BST.
   if (isBST (root, INT_MIN, INT_MAX) == true) {
      return size (root);
   }
   // Find largest BST in left and right subtrees.
   return max (largestBST (root->left), largestBST (root->right));
}
int main () {
   struct Node *root = newNode (67);
   root->left = newNode (72);
   root->right = newNode (77); root->left->left = newNode (57);
   printf ("Size of the largest BST is %d", largestBST (root));
   return 0;
}

Output

Size of the largest BST is 2

Conclusion

In this question, we learned what is binary tree and binary search tree, and how to find the largest BST in a given binary tree with the help of recursion. With the help of recursion, we will find out whether the subtree under each node is a BST and return the corresponding value.

The above is the detailed content of Translate Largest BST in a Binary Tree in C++. For more information, please follow other related articles on the PHP Chinese website!