Largest bst in binary tree

#1

how can we correct this code
only 1 test case passed

#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.

refer this https://ide.codingblocks.com/s/602169

#3

do u still have any doubts??

#4

can it be solve in o(n) ??

#5

yes… we can do it… refer this https://onlinegdb.com/GF0-AjUf5
actually i was facing some issues with coding blocks ide so i saved at some other online ide and sharing

#6


ye wala toh op galat de rha h

#7

share ur code… galt dena to ni chahiye

#8

nii ho gya m galat bna rha tha
thank u …

#9

okay… cool…

#10

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.