Write an algorithm for Breadth-first-search.

A breadth-first-search is one which starts from root node and crawls down exploring neighboring nodes.

Solution #1: We can use a queue to perform BFS. Here is the algorithm,

- Enqueue root node
- Dequeue a node and check it:
    - if it is a match, then return success
    - else enqueue it's children
- Check if queue is empty, if it's empty then return failure, otherwise repeat step 2.

Below is the code,

void bfs(struct node* root)
{
    queue q;

    q.push(root);

    while(!q.empty())
    {
        struct node* temp = q.front();
        q.pop();
        
        printf("%d ", temp->data);

        if(temp->left != NULL)
            q.push(temp->left);

        if(temp->right != NULL)
            q.push(temp->right);
    }

    printf("\n");
}

Given a sorted array in ascending order, write a function to create a binary tree having minimal height from this array.

Solution #1: We are asked to create a balanced tree to keep the height minimal. The balanced tree can be created by inserting the middle element first and then subsequently adding the left and right half of the array. This problem again demands recursion. The algorithm will look like this:-

- Insert middle element
- Insert left-half
- Insert right-half

Here is the code,

int arr[100] = {0,};

void insertArrElement(node **ptrRoot, int* arrPtr, int start, int end)
{
    if(start > end)
        return;

    int mid = (start+end)/2;
    insert(ptrRoot, arr[mid]);
    insertArrElement(&((*ptrRoot)->left), arrPtr, start, mid-1);
    insertArrElement(&((*ptrRoot)->right), arrPtr, mid+1, end);

    return;
}

int main()
{
    int i=0;
    for(i=0; i<100; i++)
        arr[i] = i;

    node* root = NULL;

    insertArrElement(&root, arr, 0, 99);
    
    return 1;
}

Write a function to check whether a tree is balanced or not.

A balanced tree is one in which no two leaf nodes differ in distance from the root node by more than one.

Solution #1: The most straight forward approach would be to calculate the maximum and minimum depth of the tree and then find out their difference. Here is the code,

int maxDepth(node* root)
{
    if(NULL == root)
        return 0;

    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);

    return 1 + (leftDepth > rightDepth ? leftDepth:rightDepth);
}

int minDepth(node* root)
{
    if(NULL == root)
        return 0;

    int leftDepth = minDepth(root->left);
    int rightDepth = minDepth(root->right);

    return 1 + (leftDepth < rightDepth ? leftDepth:rightDepth);
}

int isBalanced(node* root)
{
    if(maxDepth(root) - minDepth(root) > 1)
        return 0;
    else
        return 1;
}