Time complexity of this brute force apporach of finding largest valid bst in a binary tree?

1

So according to this post the worst case time complexity of brute force solution is O(n^2) but how? It should be O(n^3) no ? since we are passing size function also

2

Hey @its_abhijeet :wave: ,
You are right only when tree is in worst case(means it is a BST), function findLargestBST will do bottom up traversal(because it will find no root to be BST for traversal from top to bottom) then every bactrack it will check function isBST so O(n^2) there and (as I was saying if given tree was BST) then for every node it will go through size(root) function thus O(N^3) but we can do simple preprocess of height of every node from its leave thus ended up with O(N^2).

1 Like