Binary Search Trees

Question 1

Count BST nodes in a given range O(h+k), k= nodes in tree, h = height of tree

Answer 1

int getCountOfNode(Node *root, int l, int h)
{
    if(root==NULL)
    {
        return 0;
    }
    if(root->data>h)
    {
        return getCountOfNode(root->left,l,h);
    }
    else if(root->dataright,l,h);
    }
    return 1 + getCountOfNode(root->left,l,h) + getCountOfNode(root->right,l,h);
}

Question 2

Check if given binary tree is a BST or not, time : O(n), spaece : O(1) - Recursion - 2 methods

Answer 2

//METHOD - 1
bool check(Node* root,int maxm,int minm)
{
    if(root==NULL)
    {
        return true;
    }

if(root->data<=minm || root->data>=maxm)
    return false;

    return check(root->left,root->data,minm) && check(root->right,maxm,root->data);
}

bool isBST(Node* root) {
    return check(root,INT_MAX,INT_MIN);
}

//METHOD - 2
bool isBST(node* root)  
{  
    static node *prev = NULL;  

    // traverse the tree in inorder fashion  
    // and keep track of prev node  
    if (root)  
    {  
        if (!isBST(root->left))  
        return false;  

        // Allows only distinct valued nodes  
        if (prev != NULL &amp;&amp; root->data <= prev->data)  
        return false;  

    prev = root;  

        return isBST(root->right);  
    }  

return true;   }