create a BST from a given level order traversal

ALGORITHM:
The first elenment is the root.All elements less than first element in the level order traversal belong to left subtree and appear in the same order as the level order traversal of left subtree.Similarly, for the right subtree.

We use recursion in a function returning the pointer to the root of the tree on passing an array containing the level order traversal .The base case is if the level order array is empty we return a NULL tree.Otherwise, we create a tree with head as the first element of the array, then we segregate all elements less than and greater than the first element in the left and right array respectively.These are the level order traversals of the left and right subtrees respectively.These are passed to the function and return the head pointers of the eft and right subtrees that are assigned to tree->left and tree-> right.

Program:
#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct tree
{
    int d;
    struct tree* left;
    struct tree* right;
};
struct tree* create_bst(int a[100],int n)
{
    if(n==0)
    {
        return NULL;
    }
    struct tree* head=(struct tree*)malloc(sizeof(struct tree));
    int l[100];
    int r[100];
    head->d=a[0];
    int j=0,k=0;
    for(int i=1;i<n;i++)
    {
        if(a[i]<a[0])
        {
            l[j++]=a[i];
        }
        else
        {
            r[k++]=a[i];
        }
    }
    head->left=create_bst(l,j);
    head->right=create_bst(r,k);
    return head;
}
void print_in(struct tree* head)
{
    if(head!=NULL)
    {
        print_in(head->left);
        printf("%d ",head->d);
        print_in(head->right);
    }
}
int main()
{
    struct tree*head;
    int a[100];
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    printf("hi");
    head=create_bst(a,n);
    printf("hi");
    print_in(head);
}


Time comlexity:
Worst case:n^2
Best case:nlogn [T(n)=2T(n/2)+O(n)]

Design a stack with operations on middle element

How to implement a stack which will support following operations in O(1) time complexity?
1) push() which adds an element to the top of stack.
2) pop() which removes an element from top of stack.
3) findMiddle() which will return middle element of the stack.
4) deleteMiddle() which will delete the middle element

Deleting an element from middle is not O(1) for array.In singly linked list, moving middle pointer in both directions is not possible. The idea is to use Doubly Linked List (DLL). We can delete middle element in O(1) time by maintaining mid pointer. We can move mid pointer in both directions using previous and next pointers.

If there are even elements in stack, findMiddle() returns the first middle element. For example, if stack contains {1, 2, 3, 4}, then findMiddle() would return 2.

/* Program to implement a stack that supports findMiddle() and deleteMiddle
in O(1) time */
#include <stdio.h>
#include <stdlib.h>
/* A Doubly Linked List Node */
struct DLLNode
{
    struct DLLNode *prev;
    int data;
    struct DLLNode *next;
};
/* Representation of the stack data structure that supports findMiddle()
in O(1) time. The Stack is implemented using Doubly Linked List. It
maintains pointer to head node, pointer to middle node and count of
nodes */
struct myStack
{
    struct DLLNode *head;
    struct DLLNode *mid;
    int count;
};
void print(struct myStack*ms)
{
    struct DLLNode *temp=ms->head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
/* Function to create the stack data structure */
struct myStack *createMyStack()
{
    struct myStack *ms =(struct myStack*)malloc(sizeof(struct myStack));
    ms->head=NULL;
    ms->count = 0;
    return ms;
};
/* Function to push an element to the stack */
void push(struct myStack *ms, int new_data)
{
    /* allocate DLLNode and put in data */
    struct DLLNode* new_DLLNode =(struct DLLNode*) malloc(sizeof(struct DLLNode));
    new_DLLNode->data = new_data;
    /* Since we are adding at the begining,
    prev is always NULL */
    new_DLLNode->prev = NULL;
    /* link the old list off the new DLLNode */
    new_DLLNode->next = ms->head;
    /* Increment count of items in stack */
    ms->count += 1;
    /* Change mid pointer in two cases
    1) Linked List is empty
    2) Number of nodes in linked list is odd */
    if (ms->count == 1)
    {
        ms->mid = new_DLLNode;
    }
    else
    {
        ms->head->prev = new_DLLNode;
        if (ms->count & 1) // Update mid if ms->count is odd
            ms->mid = ms->mid->prev;
    }
    /* move head to point to the new DLLNode */
    ms->head = new_DLLNode;
}
int deletemid(struct myStack *ms)
{
    struct DLLNode* m=ms->mid;
    if(m!=NULL)
    {
        if(ms->count==1)
        {
            ms->mid=NULL;
            ms->head=NULL;
        }
        ms->count--;
        if(m->prev!=NULL)
        {
            m->prev->next=m->next;
        }
        if(m->next!=NULL)
        {
            m->next->prev=m->prev;
        }
        if(ms->count%2==0)
        {
            ms->mid=m->next;
        }
        else if(ms->count%2!=0)
        {
            ms->mid=m->prev;
        }
        free(m);
    }
}
/* Function to pop an element from stack */
int pop(struct myStack *ms)
{
    /* Stack underflow */
    if (ms->count == 0)
    {
        printf("Stack is empty\n");
        return -1;
    }
    struct DLLNode *head = ms->head;
    int item = head->data;
    ms->head = head->next;
// If linked list doesn't become empty, update prev
// of new head as NULL
    if (ms->head != NULL)
        ms->head->prev = NULL;
    ms->count -= 1;
// update the mid pointer when we have even number of
// elements in the stack, i,e move down the mid pointer.
    if (!((ms->count) & 1 ))
        ms->mid = ms->mid->next;
    free(head);
    return item;
}
// Function for finding middle of the stack
int findMiddle(struct myStack *ms)
{
    if (ms->count == 0)
    {
        printf("Stack is empty now\n");
        return -1;
    }
    return ms->mid->data;
}
// Driver program to test functions of myStack
int main()
{
    /* Let us create a stack using push() operation*/
    struct myStack *ms = createMyStack();
    char c[2]="a";
    int n;
    while(c[0]!='q')
    {
        scanf("%s",c);
        if(c[0]=='i')
        {
            scanf("%d",&n);
            push(ms,n);
            print(ms);
            continue;
        }
        if(c[0]=='p')
        {
            pop(ms);
            print(ms);
        }
        if(c[0]=='m')
        {
            n=findMiddle(ms);
            if(n!=-1)
            {
                printf("%d\n",n);
            }
            print(ms);
        }
        if(c[0]=='d')
        {
            deletemid(ms);
            print(ms);
        }
    }
    return 0;
}

 

Program to count leaf nodes in a binary tree

getLeafCount(node)
1) If node is NULL then return 0.
2) Else If left and right child nodes are NULL return 1.
3) Else recursively calculate leaf count of the tree using below formula.
    Leaf count of a tree = Leaf count of left subtree + 
                                 Leaf count of right subtree

Implementation:

#include <stdio.h> #include <stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Function to get the count of leaf nodes in a binary tree*/ unsigned int getLeafCount(struct node* node) { if(node == NULL) return 0; if(node->left == NULL && node->right==NULL) return 1; else return getLeafCount(node->left)+getLeafCount(node->right); } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /*Driver program to test above functions*/ int main() { /*create a tree*/ struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); /*get leaf count of the above created tree*/ printf("Leaf count of the tree is %d", getLeafCount(root)); getchar(); return 0; }

Time Complexity : O(n)
Proof:
T(n) = T(k) + T(n – k – 1) + c
Where k is the number of nodes on one side of root and n-k-1 on the other side.
Let’s do analysis of boundary conditions
Case 1: Skewed tree (One of the subtrees is empty and other subtree is non-empty )
k is 0 in this case.
T(n) = T(0) + T(n-1) + c
T(n) = 2T(0) + T(n-2) + 2c
T(n) = 3T(0) + T(n-3) + 3c
T(n) = 4T(0) + T(n-4) + 4c
…………………………………………
………………………………………….
T(n) = (n-1)T(0) + T(1) + (n-1)c
T(n) = nT(0) + (n)c
Value of T(0) will be some constant say d. (traversing a empty tree will take some constants time)
T(n) = n(c+d)
T(n) = (-)(n) (Theta of n)
Case 2: Both left and right subtrees have equal number of nodes.
T(n) = 2T(|_n/2_|) + c
This recursive function is in the standard form (T(n) = aT(n/b) + (-)(n) ) for master method http://en.wikipedia.org/wiki/Master_theorem. If we solve it by master method we get (-)(n)
Auxiliary Space : If we don’t consider size of stack for function calls then O(1) otherwise O(n).

Find The Maximum Sum in Triangle From Top to Bottom (Euler Problem).

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Brute Force

When answering the problem with a brute force solution, it is pretty simple to go through the steps, we just need to try all combinations. Since we have a binary choice each time. We can iterate through all possibilities with a normal integer counter, and use the bits of the number to pick the direction left or right. While running through the path, we sum up the numbers and check if they are larger than the current maximum found.It is not possible to try every route to solve this problem (where the base of the triangle has 100 numbers), as there are 2^(99) altogether! If you could check one trillion (10^(12)) routes every second it would take over twenty billion years to check them all.

Dynamic Programming

 
Standing at the top of the triangle we have to choose between going left and right. In order to make the optimal choice (which maximizes the sum), we would have to know how large a sum we can get if we go either way. We have to solve the two smaller problems which I have marked with blue and the orange in the figure to the right.


We can break each of the sub-problems down in a similar way, and we can continue to do so until we reach a sub-problem at the bottom line consisting of only one number, then the answer is the number it self. Once that question is answered we can move up one line, and answer the questions posed there with a solution which is a + max(b,c).
Once we know the answer to all 3 sub-problems on the next to last line, we can move up and answer the posed sub-problems by the same formula already applied. And we can continue to do so until we reach the original question of whether to go left or right

Savings with Dynamic Programming

If we want to solve the small problem with brute force, we would need to test all 8 paths, each resulting in 3 additions, in total 24 additions.
If we use dynamic programming, the first iteration would require 3 maximum comparison operations and 3 additions. The next line would require 2 maximum comparison operations and 2 additions, and the first line would require one of each. So a total of 6 maximum comparison operations and 6 additions.

Dynamic Programming – The Algorithm

We can make a short-cut with the algorithm, as we don’t have to break the problem into sub-problems, but can start from the bottom and work the way up through the triangle until we reach the top and the algorithm spits out a number.
We start with a triangle that looks like

3
7 4
2 4 6
8 5 9 3

Applying the algorithm to the small problem we will need three iterations. The first iteration we apply the rule a + max(b,c) which creates a new triangle which looks as

3
7 4
10 13 15

Making the second iteration of the algorithm makes the triangle look

3
20 19

And if we run the algorithm once more, the triangle collapses to one number – 23 – which is the answer to the question.

Program:

#include<stdio.h>
int main(void)
{
    int j,t,n,i,a[100][100];
    printf("hi\n");
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            for(j=0;j<=i;j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        for(i=n-2;i>=0;i--)
        {
            for(j=0;j<=i;j++)
            {
                a[i][j]+=a[i+1][j]>a[i+1][j+1]?a[i+1][j]:a[i+1][j+1];
            }
        }
        printf("%d\n",a[0][0]);
    }
    return 0;
}
Time complexity:O(n^2) where n is the number of rows.
we traverse through  n-1  elements on (n-2)th line, (n-2) elements on (n-3)th line and so on till 1 element in first line, a total of 1+2+..+(n-1) elements i.e. (n-1)n/2 or O(n^2) eelments.
At each element, an adition and comparision operation is performed in O(1) time.

Given an array of of size n and a number k, finds all elements that appear more than n/k times

Given an array of size n, find all elements in array that appear more than n/k times. For example, if the input arrays is {3, 1, 2, 2, 1, 2, 3, 3} and k is 4, then the output should be [2, 3]. Note that size of array is 8 (or n = 8), so we need to find all elements that appear more than 2 (or 8/4) times. There are two elements that appear more than two times, 2 and 3.
A simple method is to pick all elements one by one. For every picked element, count its occurrences by traversing the array, if count becomes more than n/k, then print the element. Time Complexity of this method would be O(n²).
A better solution is to use sorting. First, sort all elements using a O(nLogn) algorithm. Once the array is sorted, we can find all required elements in a linear scan of array. So overall time complexity of this method is O(nLogn) + O(n) which is O(nLogn).
Following is an interesting O(nk) solution:
We can solve the above problem in O(nk) time using O(k-1) extra space. Note that there can never be more than k-1 elements in output (Why?). There are mainly three steps in this algorithm.
1) Create a temporary array of size (k-1) to store elements and their counts (The output elements are going to be among these k-1 elements). Following is structure of temporary array elements.

struct eleCount {
    int element;
    int count;
}; 
struct eleCount temp[]; 

This step takes O(k) time.
2) Traverse through the input array and update temp[] (add/remove an element or increase/decrease count) for every traversed element. The array temp[] stores potential (k-1) candidates at every step. This step takes O(nk) time.
3) Iterate through final (k-1) potential candidates (stored in temp[]). or every element, check if it actually has count more than n/k. This step takes O(nk) time.
The main step is step 2, how to maintain (k-1) potential candidates at every point?  
We increment the count of an element if it is already present in array, else if there is an empty position we nsert it there and set the count to 1,else we decrement count of all elements by 1.

Consider k = 4, n = 9 
Given array: 3 1 2 2 2 1 4 3 3 

i = 0
         3 _ _
temp[] has one element, 3 with count 1

i = 1
         3 1 _
temp[] has two elements, 3 and 1 with 
counts 1 and 1 respectively

i = 2
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 1 respectively.

i = 3
         - - 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.

i = 4
         - - 2 
         - - 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 3 respectively.

i = 5
         - - 2 
         - 1 2 
         3 1 2
temp[] has three elements, 3, 1 and 2 with
counts as 1, 2 and 3 respectively. 

Now the question arises, what to do when temp[] is full and we see a new element – we remove the bottom row from stacks of elements, i.e., we decrease count of every element by 1 in temp[]. We ignore the current element.

i = 6
         - - 2 
         - 1 2 
temp[] has two elements 1 and 2 with
counts as 1 and 2 respectively.

i = 7
         - - 2 
         3 1 2 
temp[] has three elements, 3, 1 and 2 with
counts as 1, 1 and 2 respectively.

i = 8
 
         3 - 2
         3 1 2 
temp[] has three elements, 3, 1 and 2 with
counts as 2, 1 and 2 respectively.

Finally, we have at most k-1 numbers in temp[]. The elements in temp are {3, 1, 2}. Note that the counts in temp[] are useless now, the counts were needed only in step 2. Now we need to check whether the actual counts of elements in temp[] are more than n/k (9/4) or not. The elements 3 and 2 have counts more than 9/4. So we print 3 and 2.
Note that the algorithm doesn’t miss any output element. There can be two possibilities, many occurrences are together or spread across the array. If occurrences are together, then count will be high and won’t become 0. If occurrences are spread, then the element would come again in temp[]. Following is C++ implementation of above algorithm.

// A C++ program to print elements with count more than n/k #include<iostream> using namespace std; // A structure to store an element and its current count struct eleCount { int e; // Element int c; // Count }; // Prints elements with more than n/k occurrences in arr[] of // size n. If there are no such elements, then it prints nothing. void moreThanNdK(int arr[], int n, int k) { // k must be greater than 1 to get some output if (k < 2) return; /* Step 1: Create a temporary array (contains element and count) of size k-1. Initialize count of all elements as 0 */ struct eleCount temp[k-1]; for (int i=0; i<k-1; i++) temp[i].c = 0; /* Step 2: Process all elements of input array */ for (int i = 0; i < n; i++) { int j; /* If arr[i] is already present in the element count array, then increment its count */ for (j=0; j<k-1; j++) { if (temp[j].e == arr[i]) { temp[j].c += 1; break; } } /* If arr[i] is not present in temp[] */ if (j == k-1) { int l; /* If there is position available in temp[], then place arr[i] in the first available position and set count as 1*/ for (l=0; l<k-1; l++) { if (temp[l].c == 0) { temp[l].e = arr[i]; temp[l].c = 1; break; } } /* If all the position in the temp[] are filled, then decrease count of every element by 1 */ if (l == k-1) for (l=0; l<k; l++) temp[l].c -= 1; } } /*Step 3: Check actual counts of potential candidates in temp[]*/ for (int i=0; i<k-1; i++) { // Calculate actual count of elements int ac = 0; // actual count for (int j=0; j<n; j++) if (arr[j] == temp[i].e) ac++; // If actual count is more than n/k, then print it if (ac > n/k) cout << "Number:" << temp[i].e << " Count:" << ac << endl; } } /* Driver program to test above function */ int main() { cout << "First Test\n"; int arr1[] = {4, 5, 6, 7, 8, 4, 4}; int size = sizeof(arr1)/sizeof(arr1[0]); int k = 3; moreThanNdK(arr1, size, k); cout << "\nSecond Test\n"; int arr2[] = {4, 2, 2, 7}; size = sizeof(arr2)/sizeof(arr2[0]); k = 3; moreThanNdK(arr2, size, k); cout << "\nThird Test\n"; int arr3[] = {2, 7, 2}; size = sizeof(arr3)/sizeof(arr3[0]); k = 2; moreThanNdK(arr3, size, k); cout << "\nFourth Test\n"; int arr4[] = {2, 3, 3, 2}; size = sizeof(arr4)/sizeof(arr4[0]); k = 3; moreThanNdK(arr4, size, k); return 0; }

Output:

First Test
Number:4 Count:3

Second Test
Number:2 Count:2

Third Test
Number:2 Count:2

Fourth Test
Number:2 Count:2
Number:3 Count:2

Time Complexity: O(nk)
Auxiliary Space: O(k)
Generally asked variations of this problem are, find all elements that appear n/3 times or n/4 times in O(n) time complexity.

print only one line in a pascal's triangle

time complexity:O(n)

We know that ith entry in a line number line is Binomial Coefficient C(line, i) and all lines start with value 1. The idea is to calculate C(line, i) using C(line, i-1). It can be calculated in O(1) time using the following.

C(line, i)   = line! / ( (line-i)! * i! )
C(line, i-1) = line! / ( (line - i + 1)! * (i-1)! )
We can derive following expression from above two expressions.
C(line, i) = C(line, i-1) * (line - i + 1) / i

So C(line, i) can be calculated from C(line, i-1) in O(1) time

Program:
#include<stdio.h>
int main(void)
{
int t;
scanf("%d",&t);
while(t--)
{
int n,i,c;
scanf("%d",&n);
c=1;
for(i=1;i<=n+1;i++)
{
printf("%d ",c);
c=c*(n-i+1)/i;
}
printf("\n");
}
return 0;
}

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged.

Algorithm - Mirror(tree):

(1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree  i.e., Mirror(left-subtree)
(3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

Program:

#include<stdio.h> #include<stdlib.h> /* A binary tree node has data, pointer to left child and a pointer to right child */ struct node { int data; struct node* left; struct node* right; }; /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*) malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /* Change a tree so that the roles of the left and right pointers are swapped at every node. So the tree... 4 / \ 2 5 / \ 1 3 is changed to... 4 / \ 5 2 / \ 3 1 */ void mirror(struct node* node) { if (node==NULL) return; else { struct node* temp; /* do the subtrees */ mirror(node->left); mirror(node->right); /* swap the pointers in this node */ temp = node->left; node->left = node->right; node->right = temp; } } /* Helper function to test mirror(). Given a binary search tree, print out its data elements in increasing sorted order.*/ void inOrder(struct node* node) { if (node == NULL) return; inOrder(node->left); printf("%d ", node->data); inOrder(node->right); } /* Driver program to test mirror() */ int main() { struct node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); /* Print inorder traversal of the input tree */ printf("\n Inorder traversal of the constructed tree is \n"); inOrder(root); /* Convert tree to its mirror */ mirror(root); /* Print inorder traversal of the mirror tree */ printf("\n Inorder traversal of the mirror tree is \n"); inOrder(root); getchar(); return 0; }