Largest BST in a binary tree

#1

hey, could you please tell me the intuition for this problem.

#2

One of the naive approaches to solve this problem could be that

  1. Check if tree with current node as root is a valid BST and if it is then return its size.
  2. If tree with current node as its root is not a valid BST, then make recursive calls to left and right sub-trees and return the maximum of values returned by these recursive calls. Condition for valid BST could be checked by creating inorder array and checking if it is sorted.

The worst case time complexity of above algorithm is O(n^2) which occurs when the binary tree is skewed one with each node having only right child which is less than its parent.

#3

u can refer this --> https://ide.codingblocks.com/s/621939

#4

if u still have any doubt do let me know…