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;
}

Is there a path from root to leaf that sums up to a value in a binary tree!!

The problem can be solved using two simple recursive calls. As we need to find a path that starts from root and ends at leaf, we can check at every call if we hit a node that is a leaf and if the sum requirement at that point matches the value of that node, then we declare success. And if any such path exists we return true and hence the 'OR' operator in the return statement.

bool sumPath(node* root, int sum)
{
    if(root == NULL)
        return false;
    if(root->lchild == NULL && root->rchild==NULL && root->data == sum)
        return true;
    return (sumPath(root->lchild, sum - root->data) || sumPath(root->rchild, sum - root->data));
}

Level Order in a Binary Tree!!

Write a function to do level order in a binary tree with a slight modification. We need to print each level's data in a separate line.
The key steps in writing such a level order function is to identify where each level ends.

In order to do that we follow the following steps:

• We use a dummy node to identify a level end and put a dummy node as soon as we are done reading that level.
• First we enter root in the queue. As root is the only node at its level, we enter a dummy node after it to signal end of level.
• So when we read back nodes from queue, as soon as we see a dummy node we know that this level has ended
• When we remove a node from queue, we enter all its children in the queue.
• And as soon as we encounter a dummy node(signaling end of current level), we enter another dummy node in the queue(this signals that we have encountered all nodes in previous level and entered their children in the queue, so this level ends here).
• As we need to print each level in new line, we enter a new line when we see a dummy node

Consider Node to be a class having 3 members, a left and right Node pointer and an integer data field and all members are public.

void printLevel(Node* root)
{
    queue<Node*> q;
    Node *dummy = NULL;
    if(root == NULL)
        return;
    //Enter root in the queue
    else
    {
        q.push(root);
        q.push(dummy);
    }
    //If queue is empty then we are done.
    while(!q.empty())
    {
        Node* temp = q.front();
        q.pop();
        //If its a dummy node
        if(temp == NULL)
        {
            cout<<endl;
            q.push(dummy);
        }
        //Else enter node's children in the queue
        if(temp->left!=NULL)
            q.push(temp->left);
        if(temp->right!=NULL)
            q.push(temp->right);
        //Print out node's data.
        cout<<temp->data<<" ";
    }
}