Doubts related to BST

#1
  1. I am not able to differentiate between top-down and bottom-up approach in case of trees. Please explain.
    2)Please share code for Bottom-up Approach for Check for BST problem.
#2

hello @sahilkhan2312000131

in case of tree the both the approaches looks almost the same(becuase even in bottom up first we need to traverse from root to leave and then from leave we start computing the results and send it to parent ).
the minute that they have is how we are computing the result.

if we are first looking for subtrees of current node and then the node itself then it is bottom up(first smaller problem, and then using them to decide the solution of current).

top down
bool isBST(node *root,int minV = INT_MIN,int maxV = INT_MAX){

if(root==NULL){

    return true;

}

if(root->data >= minV && root->data<=maxV && isBST(root->left,minV,root->data) && isBST(root->right,root->data,maxV)){

    return true;

}

return false;
}

…

bottom up
tuple  isBst(node *root){  // tuple will store {min,max,isbst)

      if(root==NULL){
                return {INT_MAX,INT_MIN,true};
      }
    
   if(root->left==NULL && root->right==NULL){  //leaf node
             return { root->data,root->data , true};
    }

tuple left =isBst(root->left);
tuple right = isBst(root->right);
if(!left.isbst || !right.isbst){   //subtree is not bst, so current node cant be bst
  return{any value,any value,false};  // now we dont care about values
  }
  
// now for current node to be bst it shoudl be greater than the left max and smaller than right min and leftnode and right node must also be bst.

  if( left.max < root->data && right.min > root->data ){
    return { min(left.min,root->data) , max(root->data,right.max),true};
   }
else{ //not a bst 
   return {any value,any value,false};
}

}
#3

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.