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

Print all possible combinations of strings that can be made using a keypad given a number

Consider a phone keypad where every number has few english alphabet characters associated with it. When a user types some numbers on screen , print all possible permutations of string possible using the characters associated with those numbers. Example: if 1 corresponds to A B C and 2 corresponds to DEF. Then number "12" might represent any of the following : AD, AE, AF, BD, BE, BF, CD, CE, CF.
The problem is very similar to this problem.
The key steps in writing an this function are:

• Initialize a keypad array of strings with alphabets corresponding to each number.
• Now one by one choose each of the characters corresponding to the number and recurse.
• Make sure to keep a check for the digit 9 as it will have only 2 characters.

string keypad[9] = {"ABC", "DEF", "GHI", "JKL", "MNO", "PQR", "STU", "VWX", "YZ"};

void keys(char* num, char *s, int start, int end)
{
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    
    s[start] = keypad[(num[start] - '0' - 1)][0];
    keys(num, s,start+1,end);
    s[start] = keypad[(num[start] - '0' - 1)][1];
    keys(num, s,start+1,end);
    if((num[start] - '0' - 1) < 8)
    {
        s[start] = keypad[(num[start] - '0' - 1)][2];
        keys(num, s,start+1,end);
    }
}

Function to print all permutations of a string!!

Write a function to print all permutations of a string. Characters in the string do not repeat themselves.
The problem is pretty similar to this problem.
Solution is a simple recursive approach where we call the function again and again once with each arrangement of characters. These arrangements are achieved by swapping start with every other character and calling the function again and again with different values of start.

void perm(string s, int start, int end)
{
    //If we have already reached the end of string, print it
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    char temp;
    for(int i=start;i<end;i++)
    {
        SWAP(s[start],s[i],temp);
        perm(s,start+1,end);
        SWAP(s[i],s[start],temp);
    }
}

Reverse a Linked List!!

Iterative version

void reverse()
{
    if(head == NULL)
        return;
    list *first = NULL;
    list *second = head;
    list *third = second->next;
    while(third!=NULL)
    {
        second->next=first;
        first = second;
        second = third;
        third = third->next;
    }
    second->next = first;
    head=second;
}

Recursive version

void rReverse(list *n)
{
    if (n == NULL)
        return;
    if(n->next ==NULL)
    {
        head = n;
        return ;
    }
    rReverse(n->next);
    n->next = n;
}

Print given string in all combinations of uppercase and lowercase characters.

Given a string we need to print the string with all possible combinations of the uppercase and lowercase characters in the string.
So given a string "abc", we need to print the following:
ABC
ABc
AbC
Abc
aBC
aBc
abC
abc
Solution is a simple recursive approach where we call the function again and again once with a character in lower case and another time with the same character in upper case. The code is similar to what we would write for all permutations of a string.

void lowerUpper(char *s, int start, int end)
{
    if(start == end)
    {
        cout<<s<<endl;
        return;
    }
    //Change next character to upper case
    s[start] = toupper(s[start]);
    lowerUpper(s,start+1,end);

    //Change the same character as changed earlier to lower case
    s[start] = tolower(s[start]);
    lowerUpper(s,start+1,end);
}

\[x^y\]

Implement a function to calculate exponentiation x^y quickly. x and y are assumed to be integers.

The key steps in writing an exponentiation function are:

• Return 1 if exponent(power) is 0 because \[x^0 = 1\]
• Return x if exponent(power) is 1 because \[x^1 = x\]
• Check if exponent is <0. If it is, then call the function again with 1/x and -y because \[x^{-y} = 1/x^y\]
• Call function again using x*x and y/2 if exponent is even. Say y = 4, we can write \[x^4 = [x^2]^2\] which is essentially calling function again using x*x and y/2.
• If exponent is odd, say y = 2n+1, we can write \[x^y = x^{2n+1} = x * x^{2n}\]Now 2n is even and we can use the even case again by just multiplying x to it.

int power(int x, int y)
{
    if( x == 0)
        return x;

    //Checking if exponent == 0
    if(y==0)
        return 1;

    //Checking if exponent == 1
    else if(y==1)
        return x;

    //Checking if exponent < 0
    else if(y<0)
        return power(1/x, -1*y);

    //Checking if exponent is even and calling function again using x*x and y/2
    else if(y%2==0)
        return power(x*x, y/2);

    //Checking if exponent is odd and calling function again by making exponent even by taking out one x and multiplying it separately and then using the even case again. 
    else
        return x*power(x*x, y/2);
}

This method runs in O(log y) time.