Useful tree functions!!

1) Check if a given tree is a BST?
Checking that a given binary tree is a BST requires fulfillment of the property that value of root node is greater than all nodes in its left subtree and its less than all nodes in its right subtree.

bool isBST(tree* root,int min, int max)
{
    if(root==NULL)
        return true;
    if((root->data >=min && root->data<max) || (root->data >min && root->data<=max))
        return isBST(root->lchild, min, root->data) && isBST(root->rchild, root->data, max);
    else
        return false;
}

2) Find height of given binary tree.
To calculate height of the tree, we find the height of the left subtree and the right subtree recursively and report the maximum of the two.

int height(tree* root)
{
    if(root==NULL)
        return 0;
    
    return (1+ max(height(root->lchild), height(root->rchild)));
}

3) Is the given binary tree balanced?
To check that a tree is balanced, we check at every node that its right subtree and its right subtree do not differ in height by more than 1. The property should hold true at all levels and for all nodes in order for tree to be balanced.

bool isBalanced(tree* root)
{
    if(root!=NULL)
    {
        int l = height(root->lchild);
        int r = height(root->rchild);
        
        if(abs(l-r)>1)
            return false;
        else
        {
            isBalanced(root->lchild);
            isBalanced(root->rchild);
        }
        return true;
    }

4) Count leaves in a binary tree.
Recursion is pretty similar to height calculation. We find number of leaves in the left subtree and sum that with number of leaves in the right subtree.

int countLeaves(struct tree* root)
{
    if(root==NULL)
        return 0;
    if(root->lchild==NULL && root->lchild==NULL)
        return 1;
    else
        return countLeaves(root->lchild) + countLeaves(root->rchild);
}

5) Given the root node, copy the binary tree.

tree* copy(tree* t1)
{
    if(t1)
    {
        tree* temp = new tree;
        
        temp->lchild=copy(t1->lchild);
        temp->data=t1->data;
        temp->rchild=copy(t1->rchild);
        return temp;
    }
    return NULL;
}