Find the size of the Largest BST in a Binary Tree
To find the largest BST in a binary tree we should be aware of the following terms:
Binary Tree: A binary tree is defined as a tree with no more than two children. Each binary tree element can only have two children, we call them the left and right child.
Binary Search Tree: A binary search tree is a data structure that allows us to keep a sorted list of numbers in a short amount of time. A binary Search tree is also called a binary tree because each BST tree node has a maximum of two children. It is also called a search tree because this can be used to search for the presence of a number in logarithmic time. There are some properties that separate a normal binary tree from BST like All nodes of the left subtree are less than the root node in Bst and all the nodes on the right subtree are greater than the root node.
Inorder Traversal: It signifies that after traversing the root node, the left subtree is visited first, followed by the right subtree. Inorder traversal refers to the process of traversing the root node between the left and right subtrees. As a result, each node in the inorder traversal gets visited in between its subtrees.
Prerequisite for this problem: To check if a tree is BST or not
Approach 1: Brute force
We must determine whether a node's left subtree contains any elements bigger than the node's value, as well as whether the node's right subtree contains any elements smaller than the node's value. We'll create two helper functions, getMin(root) and getMax(root), that return the tree's minimal and maximum values for a given root. Then we'll look at each node If the value of the node is greater than or equal to the maximum value in the left subtree Is the node's value less than or equal to the right subtree's minimum value? We'll basically see if this expression is true or not: getMax(root.left)<root.val< getMin(root.right).We are traversing and calling getMax(root.left) and getMin(root.right) for each node.We are traversing and calling getMax(root.left) and getMin(root.right) for each node hence it will cost quadratic time complexity.
Approach 2:Optmized approach
We traversed several portions of the tree many times in the prior approach. We go down the tree, keeping track of the min and max allowable values for each node, rather than executing getMin(root) and getMax(root) for each node. We do this by passing the allowable range as a function argument and recursing through the left and right subtrees. We're only looking at each node once, hence the min and max values should be INT MIN and INT MAX. Here each node is visited only once hence it will cost only linear time complexity.
Approach 3:Using inorder Traversal
We know that traversing a binary search tree in an inorder way will result in sorted order of its elements. We'll take advantage of this by traversing the tree in reverse order and storing the elements in an array. The array will then be traversed in a linear fashion to see if it is in sorted order.Inorder traversal of BST for storing elements in arr[] + Single loop to check arr[] is sorted or not = O(n) + O(n) = O(n)
Now since we are aware of how to check if a subtree is a binary search tree or not then we can move with our main problem of finding the largest bst in binary tree search. So let’s explore all the different ways to solve this problem.
Approach 1
Start from the root node and do an inorder traversal for the entire tree. For each node X, check whether the subtree rooted with X is a binary search tree or not. If it is a Binary Search Tree, then return the size of the subtree rooted with X. Else, recursively work down the left and right subtrees and return the maximum of values returned by the left and right subtrees. The worst-case time complexity for this approach will reach O(n^2) if we consider a skewed tree for worst-case analysis.
Approach 2
The time complexity of this approach is O(n2), where n is the size of the Binary Search Tree and requires space proportional to the tree’s height for the call stack. We can improve time complexity to O(n) by traversing the tree in a bottom-up manner where information is exchanged between the child nodes and parent node, which helps determine if the subtree rooted under any node is a BST in constant time.
There is one more optimized approach that can solve this problem in linear time. The important point to remember is that if a subtree is a BST, then all nodes in its subtree are likewise BSTs. As a result, we'll recurse down the binary tree, using the information from the left and right subtrees to store the information for the current subtree.
In method 1, we have traversed the tree in a top-down manner and have done a Binary Search Tree test for every individual node, but as explained above, If we traverse the tree from a bottom or in a bottom-up manner, then we can pass information about subtrees to their respective parent. The passed information or data can be used by the parent node to do the Binary Search Tree test (for the parent node) only in constant time or, I would say, O(1) time. A left subtree needs to tell the parent whether it is a Binary Search Tree or not, and it also needs to pass the maximum value in it. Hence, one can compare the maximum value with the parent’s data to check the Binary Search Tree property. Now Similarly, the right subtree also needs to pass the minimum value up to the tree. The subtrees need to pass the following information up to the tree to find the largest BST in all BSTS.
