Given a binary tree, count the number of binary search trees present in it

Question

A binary tree is given and we have to count the number of binary search trees in it.Every leaf node is a BST
I used the following approach.
for every node in bt check if it is bst or not
The time complexity for above approach is O(n²).How can we do it in an efficient way O(n).

Answer 1

If I understood the question correctly, this can be solved as follows; one would aim at counting the number of nodes which are the root of a binary seach tree. As already remarked, every leaf is trivially the root of a binary search tree. A non-leaf node a is the root of a binary search if and only if the left child of a is a binary search tree, the right child of b is the root of a binary search tree and the maximum over all values under the left child of a is not greater than the value of a and the minumum over all values under the right child of a are larger or equal to the value of a. Evaluation of this property can be done by a recursive evaluation which visits every node exactly once, which results in a linear runtime bound.

Answer 2

A straightforward recursive traversal of the tree returning a few extra pieces of data may help manage it in O(n) time, n being the number of nodes. Below you can find an implementation in Python.

numBST = 0
def traverse(root):
    global numBST
    leftComplies = True
    rightComplies = True
    rootRange = [root.val, root.val]
    if root.left != None:
        leftResult = traverse(root.left)
        leftComplies = leftResult[0] and leftResult[1][1] < root.val
        rootRange[0] = leftResult[1][0]
    if root.right != None:
        rightResult = traverse(root.right)
        rightComplies = rightResult[0] and rightResult[1][0] > root.val
        rootRange[1] = rightResult[1][1]
    if leftComplies and rightComplies:
        numBST += 1
    return (leftComplies and rightComplies, rootRange)

After you run traverse with root of the binary tree as parameter, numBST will contain the number of BSTs within the root.

The function traverse given above recursively traverses the tree root of which is given to it as a parameter. For each node V, if V has a left child L, it recursively traverses the left child and returns some data. Specifically, it returns a list of length 2. The first element in the list is a boolean value indicating whether the left subtree rooted in L is a BST. Second element of the returned list contains another list containing the smallest and the largest value, respectively, in the subtree rooted in L.

For the tree rooted in V to be a BST, the subtree rooted in L must also be a BST AND the largest value in the subtree rooted in L(hence all the values in that subtree) must be smaller than the value stored in V. So after recursively calling traverse for L, we check the returned data to find out if these conditions are satisfied.

Similarly, if there is a right child R of V, it is recursively traversed. To be a BST, the tree rooted in V must also satisfy the condition that the tree rooted in R is a BST AND the smallest node of subtree rooted in R(hence all the nodes in that subtree) contains a value that is larger than the value stored in V.

If all these conditions are satisfied, the tree rooted in V can be considered as a BST and the result, stored in numBST, is updated accordingly. Note that we also update the smallest and largest values stored in V as we recursively traverse its children L and R, and perform the checks mentioned above, so that we pass the correctly updated values to the higher levels of recursion.