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).