Find all the ancestor nodes of  a node in BT.

void findAncestorsOfNode( Node node, int[] arr, int val, int length){

if( node == null){
return ;
}

arr[length++] = node.getValue();

if( node.getValue() == val ){

for( int i = 0 ; i < length-1 ; i++){
System.out.print( arr[i] + "  ");
}
System.out.println();
return ;

}else{
findAncestorsOfNode( node.getLeftNode(), arr, val, length);
findAncestorsOfNode( node.getRightNode(), arr, val, length);
}

}

Find the depth of a node in BT iteratively.

int depthOfNode( Node node, int val){

if ( node == null){

return 0;

}

int count = 1;

Queue<Node> queue = new LinkedList<Node>();

queue.add(node);

queue.add(null);

while( !queue.isEmpty() ){

Node temp = queue.poll();

if( temp != null ){

if( temp.getValue() == val){

return count;

}

if( temp.getLeftNode() != null){

queue.add(temp.getLeftNode());

}

if( temp.getRightNode() != null){

queue.add(temp.getRightNode());

}

} else {

if( !queue.isEmpty()){

count++;

queue.add(null);

}

}

}

return 0;

}

Doubly Linked List Implementation in C




# include <stdio.h>
# include <conio.h>


struct node{
    struct node* prev ;
    int value;
    struct node* next;
};

void appendNode( struct node **head, int val);
void addAtBegin( struct node **head, int val);
void display_forward_dll( struct node **head);
void display_reverse_dll( struct node **head);


int main(){

struct node *head;

head = NULL;

appendNode( &head, 1);
appendNode( &head, 2);
appendNode( &head, 3);
appendNode( &head, 4);
appendNode( &head, 5);

display_forward_dll(&head);
display_reverse_dll(&head);

addAtBegin( &head, 100);
addAtBegin( &head, 200);
addAtBegin( &head, 300);

display_forward_dll(&head);
display_reverse_dll(&head);

return 0;
}

void appendNode( struct node **head, int val){

    if( *head == NULL){
        struct node *temp = (struct node*)malloc(sizeof(struct node));
        temp->prev = NULL;
        temp->value = val;
        temp->next = NULL;
        *head = temp;
    } else {
        struct node *temp = (struct node*)malloc(sizeof(struct node));
        temp->next = NULL;
        temp->value = val;
        struct node *temp1 = *head;
        while( temp1->next != NULL ){
            temp1 = temp1->next;
        }
        temp1->next = temp;
        temp->prev = temp1;
    }

}

void addAtBegin( struct node **head, int val){

    if( *head == NULL ){
        struct node *temp = (struct node*)malloc(sizeof(struct node));
        temp->prev = NULL;
        temp->value = val;
        temp->next = NULL;
        *head = temp;
    } else {
        struct node *temp1 = *head;
        struct node *temp = (struct node*)malloc(sizeof(struct node));
        temp->prev = NULL;
        temp->value = val;
        temp->next = temp1;
        *head = temp;
    }
}

void display_forward_dll( struct node **head){

    if( *head == NULL){
        printf( "[DOUBLY_LINKED_LIST] is empty\n");
    } else {
        struct node *temp = *head;
        while( temp != NULL){
            printf("[DOUBLY_LINKED_LIST] element in forward is %d \n", temp->value);
            temp = temp->next;
        }
    }
}


void display_reverse_dll( struct node **head){

    if( *head == NULL){
        printf( "[DOUBLY_LINKED_LIST] is empty\n");
    } else {
        struct node *temp = *head;
        while( temp->next != NULL){
            temp = temp->next;
        }
        while( temp->prev != NULL){
            printf("[DOUBLY_LINKED_LIST] element in reverse is %d \n", temp->value);
            temp = temp->prev;
        }

    }
}

Queue Implementation in C




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

struct node {
    int value;
    struct node *next;
};

typedef enum { false, true } bool;

void enqueue( struct node **head, struct node **rear, int val);
int dequeue( struct node **head, struct node **rear);
void display_queue( struct node **head, struct node **rear);
int queueSize( struct node **head, struct node **rear);
bool isEmpty( struct node **head, struct node **rear);


int main(){

struct node *head, *rear;

head = NULL;
rear = NULL;


enqueue_c( &head, &rear, 1);
enqueue_c( &head, &rear, 2);
enqueue_c( &head, &rear, 3);
enqueue_c( &head, &rear, 4);

display_queue_c(&head, &rear);

printf("[DEQUEUE] of QUEUE is %d\n", dequeue_c( &head, &rear));
printf("[DEQUEUE] of QUEUE is %d\n", dequeue_c( &head, &rear));
printf("[DEQUEUE] of QUEUE is %d\n", dequeue_c( &head, &rear));

display_queue_c(&head, &rear);


return 0;
}

void display_queue( struct node **head, struct node **rear){

    if( *head == NULL && *rear == NULL){
        printf("[QUEUE] is empty\n");
    } else {
        struct node *temp = *head;
        struct node *temp1 = *rear;
        while( temp != temp1){
            printf("[QUEUE] value is %d\n", temp->value);
            temp = temp->next;
        }
        if( temp1 != NULL){
            printf("[QUEUE] value is %d\n", temp1->value);
        }
    }

}

void enqueue( struct node **head, struct node **rear, int val ){

    if( *rear == NULL){
        struct node *temp = (struct node*)malloc(sizeof(struct node));
        temp->value = val;
        temp->next = NULL;
        *rear = temp;
        *head = *rear;
    } else {
        struct node *temp = (struct node*)malloc(sizeof(struct node));
        temp->value = val;
        struct node *temp1 = *rear;
        temp1->next = temp;
        //printf("[DBG]: after modifying  %d\n", temp->value);
        *rear = temp;
    }
}


int dequeue(struct node **head, struct node **rear){

    if( *head == NULL){
        printf("[QUEUE] is empty\n");
        return -1;
    } else {
        struct node *temp = *head;
        struct node *temp1 = *head;
        temp1 = temp1->next;
        *head = temp1;
        return temp->value;
    }

}


int queueSize( struct node** head, struct node** rear){

    int count = 0;

    if( *head == NULL){
        printf("[QUEUE] is empty\n");
        return count;
    } else {
        struct node* temp ;
        temp = *head;
        while( temp != *rear){
            count += 1 ;
            temp = temp->next;
        }
        count++;
        return count;
    }
}


bool isEmpty( struct node** head, struct node** rear){

    if( *head == NULL && *rear == NULL){
        return true;
    }else{
        return false;
    }
}

Stack Implementation in C




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

struct node {
    int value;
    struct node* next;
};

void display_stack( struct node** head);
int count( struct node **head);
void push( struct node** head, int val);
int pop( struct node** head);



int main(){

struct node *head;
head = NULL;
int item;

push(&head, 1);
push(&head, 2);
push(&head, 3);
push(&head, 4);
push(&head, 5);

display_stack( &head);

printf("The length of [STACK] is %d\n", count(&head));

printf("The element popped of [STACK] is %d\n", pop(&head));
printf("The element popped of [STACK] is %d\n", pop(&head));
printf("The element popped of [STACK] is %d\n", pop(&head));

printf("The length of [STACK] is %d\n", count(&head));

display_stack( &head);

return 0;
}


void display_stack( struct node** head){

    struct node* temp = *head;
    while( temp != NULL ){
        printf("The element in [STACK] is %d\n", temp->value);
        temp = temp->next;
    }
}


int count( struct node **head){
    struct node *temp;
    temp = *head;
    int count = 0;
    while( temp != NULL){
        count++;
        temp = temp->next;
    }
    return count;
}


void push( struct node** head, int val){

    struct node *temp;
    temp = (struct node*)malloc(sizeof(struct node));
    temp->value = val;
    temp->next = *head;
    *head = temp;
}


int pop( struct node** head){

    if( *head == NULL){
        printf( "The stack is empty");
        return 0;
    } else {
        struct node *temp = *head;
        *head = (*head)->next;
        return temp->value ;
    }
}

Linked List Implementation in C




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

struct node {
    int value;
    struct node* next;
};

void display( struct node** head);
void appendNode( struct node** node1, int val);
void addAtBeginning( struct node** head, int val);
int listLength( struct node** head);
void addNodeAtLocation( struct node** head, int loc, int val);
void reverseList( struct node** head);

int main(){

struct node* head ;
head = NULL ;

//clrscr();

appendNode( &head, 1);
appendNode( &head, 2);
appendNode( &head, 3);
appendNode( &head, 4);
appendNode( &head, 5);
appendNode( &head, 6);

printf("The length of the list is %d \n", listLength(&head) );

display( &head);

reverseList( &head);

display( &head);

printf("The node at 1st is %d \n",getNodeAtLocation( &head, 1));
printf("The node at 2nd is %d \n",getNodeAtLocation( &head, 2));
printf("The node at 3rd is %d \n",getNodeAtLocation( &head, 3));
printf("The node at 4th is %d \n",getNodeAtLocation( &head, 4));

addNodeAtLocation( &head, 3, 400);
addNodeAtLocation( &head, 5, 500);

addAtBeginning( &head, 100);
addAtBeginning( &head, 200);

printf("The node at 1st is %d \n",getNodeAtLocation( &head, 1));
printf("The node at 2nd is %d \n",getNodeAtLocation( &head, 2));
printf("The node at 3rd is %d \n",getNodeAtLocation( &head, 3));
printf("The node at 4th is %d \n",getNodeAtLocation( &head, 4));

addNodeAtLocation( &head, 3, 400);
addNodeAtLocation( &head, 5, 500);

printf("The length of the list is %d\n", listLength(&head) );
display( &head);

return 0;
}

int getNodeAtLocation(struct node** head, int loc){
    struct node* temp;
    temp = *head;
    int i ;
    for( i = 1; i < loc ; i++){
        temp = temp->next;
    }

    return temp->value;
}

void addNodeAtLocation( struct node** head, int loc, int val){
    struct node *temp, *temp1;
    temp = *head;
    int i ;
    for( i = 1; i < loc ; i++){
        temp = temp->next;
    }


    temp1 = (struct node*)malloc(sizeof(struct node));
    temp1->value = val;
    temp1->next = temp->next;
    temp->next = temp1;

}

void addAtBeginning( struct node** head, int val){

    struct node* temp;
    temp = (struct node*)malloc(sizeof(struct node));
    temp->next = *head;
    temp->value = val;
    *head = temp;

}

void display( struct node** head){

    struct node* temp ;

    if( *head == NULL){
        printf("The linked list is empty \n");
    }

    temp = *head;

    while( temp != NULL){
        printf("The value is %d\n", temp->value );
        temp = temp->next;
    }

}

void appendNode( struct node** node1, int val){

    struct node* temp;
    struct node* temp1;

    if( *node1 == NULL){
        temp = (struct node*)malloc(sizeof(struct node));
        temp->value = val;
        temp->next = NULL;
        *node1 = temp;
    } else {
        temp1 = *node1;
        while( temp1->next != NULL){
            temp1 = temp1->next;
        }
        temp = (struct node*)malloc(sizeof(struct node));
        temp->value = val;
        temp->next = NULL;
        temp1->next = temp;

    }

}

int listLength( struct node** head){

    struct node* temp;
    temp = *head ;
    int length = 0;

    if(*head == NULL){
        return length;
    } else {
       while( temp != NULL){
            length++;
            temp = temp->next;
       }
       return length;
    }

}

void reverseList( struct node** head){
    struct node *temp, *temp2, *temp3;
    temp = *head;
    temp3 = NULL;

    if( temp == NULL || listLength(head) == 1 ){
       return;
    }

    while( temp != NULL){
        temp2 = temp->next;
        temp->next = temp3;
        temp3 = temp;
        temp = temp2;
    }

    *head = temp3;
}

Level Traversal for a BT iteratively.

Very important function to find  max/min, node count, check for a node if exists.


private void iterativeLevelTraversal( Node node){

Queue<Node> queue = new LinkedList<Node>();
Node temp_node = root ;

// we can find min-max//comparing leaf elements.

while( temp_node != null){

// write all your check functions over here.
                // it can be finding the max/min, node count,
                // check if the node exists, find the sum of nodes many such....!

System.out.print( temp_node.getValue() + "  ");

if( temp_node.getLeftNode() != null){
queue.add( temp_node.getLeftNode());
} 
if( temp_node.getRightNode() != null){
queue.add( temp_node.getRightNode());
}

temp_node = queue.poll();
}

}

Code to print paths from root to all leaves in the BT recursively.


private void printRootToLeafNodes( Node node, int[] arr, int length ){

if( node == null){
return;
}

arr[length++] = node.getValue();

if( node.getLeftNode() == null && node.getRightNode() == null){
for( int i = 0; i < length ; i++){
System.out.print( arr[i] + "  ");
}
System.out.println();
return;
} else {
printRootToLeafNodes(node.getLeftNode(),  arr, length );
printRootToLeafNodes(node.getRightNode(), arr, length );
}

}

During times of crisis I always try to reinvent myself. Where I go and revisit my basics.
As a part of that I am gonna populate my blog with lots of Algorithms and Data Structures.

Going forward I am gonna share some important frameworks I have worked on and developed.

I am strong believer of  thought  "After winter comes the spring".

Before starting the blog just say "Jai Bolo Ganesh Maharaj Ki".