[Solved]-Using Bnode Class Write Recursive Code Compute Height Bst Rooted Given Node U Int Ht Bnode Q37271139

Using the same BNode class as below, write the recursive code tocompute the height of the BST rooted at any given node u:

int ht(BNode u){…} Remember that the height of a null node is−1.

**Note-The answer to the above question is based on a questionwhich I already have the answer for (you don’t have to answer it).Just read the question and answer to part A below so you can answerthe above question (part B)

Question:

Consider the following BNode class:

class BNode {

int val;

BNode left, right;
…

boolean isBST(BNode u){…}
boolean isBST(int min, BNode u, int max){…}

}

Note that our BNodes do not have parent pointers! It has amethod isBST(u) that returns true if the subtree rooted at u is aBST. Please write the code for isBST(u) and its helper methodisBST(min, u, max) which will return false if the keys in thesubtree at u do not lie in the range (min, max). The helper methodmust be recursive.

Answer:

int isBST(BNode root)

{

    // if the tree is empty

    if(root ==null)

        returntrue;

    // if the current node disobeys the BSTproperty

    if(root.left !=null &&root.left.value>root.value)

        returnfalse;

    // if the current node disobeys the BSTproperty

    if(root.right !=null &&root.right.value<root.value)

        returnfalse;

    // recursively check if the right and leftsubtree also are in BST

    if(isBST(root.left)!= true ||isBST(root.right)!= true )

        returnfalse;

    // if the tree is BST

    returntrue;

}

boolean isBST(int min, BNodeu, int max)

{

    if( u== null )

        returntrue;

   

    // if the current node is outside therange

    if(u.value < min|| u.value >max )

        returnfalse;

   

    // recursively check if the right and leftsubtree also are in BST

    if(isBST(min,root.left, max)!= true ||isBST(min,root.right, max)!= true )

        returnfalse;

   

    returntrue;

}

Expert Answer

---

Answer to Using the same BNode class as below, write the recursive code to compute the height of the BST rooted at any given node … . . .