Print Left and Right View of a Binary Tree

I will be putting some of interesting problems of Data-Structure and Algorithms that I encounter during my reading or while having some interesting discussions with my friends.

Today, I will post a problem on "How to print the left view and right view of a Binary Tree".

    Left View or Right View of a Binary Tree is a list of nodes visible if we see this tree from left side or a right side respectively. For example, for the Binary Tree shown in C program below, Left-View is {1 2 4 7 8 9 10 11} and Right-View is {1 3 6 7 8 9 10 12}. 

Approach:

    We do a Breadth First Search (BFS) on given binary tree and while doing the BFS on it, we maintain the level info for each node. Now for the left-view, we note the node info in left-view-array when we make our first move to next level. Similarly for the right-view, we note the node info in right-view-array when we leave a given level and are moving to next level. Last node in BFS is always the last node in Right-view !!

#include<stdio.h>
#include<stdlib.h>

#define MAX 100

struct node{
    int data;

    struct node* left;
    struct node* right;
};

struct node* queuePtr[MAX];
int levels[MAX], leftView[MAX], rightView[MAX];
int front, end, lc, rc;

struct node* getNode () {
    struct node *t = (struct node*) malloc(sizeof(struct node));
    t->left = t->right = NULL;

    return t;
}

int isLast(int index) {
    return ( (index+1) == end) ? 1 : 0 ;
}

// To be called once node with index is expanded
void isCand(int index) {
    if (index==0) {
        leftView[lc++] = queuePtr[index]->data;
        rightView[rc++] = queuePtr[index]->data;

        return;
    }
    if (levels[index] > levels[index-1]) {
        leftView[lc++] = queuePtr[index]->data;
    }
    if ( !isLast(index) && (levels[index+1] > levels[index]) ) {
        rightView[rc++] = queuePtr[index]->data;
    } else if (isLast(index)) {
        rightView[rc++] = queuePtr[index]->data;
    }
}

void print_Left_and_Right_View() {
    int i;

    lc = rc = 0;
    levels[front] = 0;
    while (front < end) {
        if (queuePtr[front] != NULL) {
            if (queuePtr[front]->left != NULL) {
                levels[end] = levels[front]+1;
                queuePtr[end++] = queuePtr[front]->left;
            }
            if (queuePtr[front]->right != NULL) {
                levels[end] = levels[front]+1;
                queuePtr[end++] = queuePtr[front]->right;
            }

           isCand(front); 
        }
        front++;
    }

    printf("Left  View : ");
    for(i=0 ; i<lc ; i++) {
        printf("%d ", leftView[i]);
    }

    printf("\nRight View : ");
    for(i=0 ; i<rc ; i++) {
        printf("%d ", rightView[i]);
    }
    printf("\n");
}

int main () {
    struct node* n1  = getNode();
    struct node* n2  = getNode();
    struct node* n3  = getNode();
    struct node* n4  = getNode();
    struct node* n5  = getNode();
    struct node* n6  = getNode();
    struct node* n7  = getNode();
    struct node* n8  = getNode();
    struct node* n9  = getNode();
    struct node* n10 = getNode();
    struct node* n11 = getNode();
    struct node* n12 = getNode();

    n1->data = 1;
    n1->left = n2;
    n1->right = n3;

    n2->data = 2;
    n2->left = n4;
    n2->right = n5;

    n3->data = 3;
    n3->left = NULL;
    n3->right = n6;

    n4->data = 4;

    n5->data = 5;
    n5->right = n7;

    n6->data = 6;

    n7->data = 7;
    n7->left = n8;

    n8->data = 8;
    n8->right = n9;

    n9->data = 9;
    n9->right = n10;

    n10->data = 10;
    n10->left = n11;
    n10->right = n12;

    n11->data = 11;
    n12->data = 12;

    /*
        How does the Tree look ?


                                     1
                                   /   \
                                  2     3
                                /   \     \
                               4     5     6    
                                      \
                                       7
                                      /
                                     8
                                      \
                                       9
                                        \
                                        10
                                       /  \
                                      11  12
    */


    // Main logic starts here ...
    front=end=0;
    queuePtr[end++] = n1;
    
    print_Left_and_Right_View();
    // Main logic ends here ...


    free(n1);
    free(n2);
    free(n3);
    free(n4);
    free(n5);
    free(n6);
    free(n7);
    free(n8);
    free(n9);
    free(n10);
    free(n11);
    free(n12);

    return 0;
}