1.> How would you check if a binary tree is balanced?

Answer :

A tree is considered balanced when the difference between the min depth and max depth does not
exceed 1.
Recursive algorithms always work well on trees, so here’s some code.
int min_depth( Node * root ) {
if( !root ) {
return 0;
}
return 1 + min( min_depth( root->left ),
min_depth( root->right ));
}

int max_depth( Node * root ) {

if( !root ) {
return 0;
}
return 1 + max( max_depth( root->left ),
max_depth( root->right ));
}

bool is_balanced( Node * root ) {

return ( max_depth( root ) - min_depth( root ) ) <= 1
}

2. > Write a C program to delete a tree (i.e, free up its nodes) 

Solutions:
  
clear(struct node* pNode)
{
if (pNode != NULL)
{
clear(pNode->left);
clear(pNode->right);
delete pNode;
}
}

3. > Write a C program to determine the number of elements (or size) in a tree.

Solution:

int tree_size(struct node* node)  { 

  if (node==NULL) 
  { 
    return(0); 
  } 
  else 
  { 
    return(tree_size(node->left) + tree_size(node->right) + 1); 
  }  } 

4. > Write a C program to find the depth or height of a tree.

Solution:
   
tree_height(mynode *p) {
   if(p==NULL)return(0);
   if(p->left){h1=tree_height(p->left);}
   if(p=>right){h2=tree_height(p->right);}
   return(max(h1,h2)+1); } 

The degree of the leaf is zero. The degree of a tree is the max of its element degrees. A binary tree of
height n, h > 0, has at least h and at most (2^h -1) elements in it. The height of a binary tree that contains
n, n>0, elements is at most n and atleast log(n+1) to the base 2.

Log(n+1) to the base 2 = h

n = (2^h - 1) 

4.> How to create a copy of a linked list? Write a C program to create a copy of a linked list. 

copy_linked_lists(struct node *q, struct node **s) {

    if(q!=NULL)
    {
        *s=malloc(sizeof(struct node));
        (*s)->data=q->data;
        (*s)->link=NULL;
        copy_linked_list(q->link, &((*s)->link));
    } }

6.> How to compare two linked lists? Write a C program to compare two linked lists. 

Answer :
int compare_linked_lists(struct node *q, struct node *r) {
    static int flag;
    
    if((q==NULL ) && (r==NULL))
    {
         flag=1;
    }
    else
    {
        if(q==NULL || r==NULL)
        {
            flag=0;
        }
        if(q->data!=r->data)
        {
            flag=0;
        }
        else
        {
           compare_linked_lists(q->link,r->link);
        }
    }
    return(flag); }

7.> If you are using C language to implement the heterogeneous linked list, what pointer
type will you use? 

Answer :

The heterogeneous linked list contains different data types in its nodes and we need a link, pointer, to
connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is
capable of storing pointer to any type as it is a generic pointer type.

8.> How would you detect a loop in a linked list? Write a C program to detect a loop in a linked list.

typedef struct node 

{ 
void *data; 
struct node *next;
}mynode; 

mynode * find_loop(NODE * head)

{ 
mynode *current = head; 
while(current->next != NULL) 
{ 
mynode *temp = head; 
while(temp->next != NULL && temp != current)
{ 
if(current->next == temp) 
{ 
printf("\nFound a loop."); 
return current; 
} 
temp = temp->next;
} 
current = current->next;
} 
return NULL; 
}

9.> How do you find the middle of a linked list? Write a C program to return the middle of a linked list

#include<stdio.h> 
#include<ctype.h> 
typedef struct node 
{ 
int value; 
struct node *next; 
struct node *prev; 
}mynode; 

void add_node(struct node **head, int value); 

void print_list(char *listName, struct node *head);
void getTheMiddle(mynode *head);

int main() 
{ 
mynode *head; 
head = (struct node *)NULL; 
add_node(&head, 1); 
add_node(&head, 10); 
add_node(&head, 5); 
add_node(&head, 70); 
add_node(&head, 9); 
add_node(&head, -99); 
add_node(&head, 0); 
add_node(&head, 555); 
add_node(&head, 55); 
print_list("myList", head); 
getTheMiddle(head); 
getch(); 
return(0); 
}

void getTheMiddle(mynode *head) 

{ 
mynode *p = head; 
mynode *q = head; 
if(q!=NULL) 
{ 
while((q->next)!=NULL && (q->next->next)!=NULL) 
{ 
p=(p!=(mynode *)NULL?p->next:(mynode *)NULL); 
q=(q!=(mynode *)NULL?q->next:(mynode *)NULL); 
q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
} 
printf("The middle element is [%d]",p->value); 
} 
}

void add_node(struct node **head, int value) 

{ 
mynode *temp, *cur; 
temp = (mynode *)malloc(sizeof(mynode)); 
temp->next=NULL; 
temp->prev=NULL; 
if(*head == NULL) 
{ 
*head=temp; 
temp->value=value; 
} 
else
{
for(cur=*head;cur->next!=NULL;cur=cur->next);
cur->next=temp;
temp->prev=cur; 
temp->value=value;
}
}

void print_list(char *listName, struct node *head) 

{ 

mynode *temp; 

printf("\n[%s] -> ", listName); 

for(temp=head;temp!=NULL;temp=temp->next)
{ 

printf("[%d]->",temp->value);
} 

printf("NULL\n");
}

10.> How do you reverse a linked list without using any C pointers?

Solution:
 One way is to reverse the data in the nodes without changing the pointers themselves. One can also
create a new linked list which is the reverse of the original linked list. A simple C program can do that for
you. Please note that you would still use the "next" pointer fields to traverse through the linked list (So in
effect, you are using the pointers, but you are not changing them when reversing the linked list).

11.> How to declare a structure of a linked list?

Solution:
   struct node 
{ 
int value; 
struct node *next;
 }; typedef struct node *mynode;

12.> What leads to code-bloating in C++?

Answer:

Inline functions and templates, if not used properly, may lead to code bloating. Multiple Inheritance may
also lead to code bloating (this is because the sub classes will end up getting members from all the base
classes even if only few members will suffice). Techniques to avoid code blot are discussed in “Effective
C++ programming”.
13.> What are references in C++? Why do you need them when you have pointers?

Answer:

  
A reference variable is actually just a pointer that reduces syntactical clumsiness related with pointers in
C (reference variables are internally implemented as a pointer; it’s just that programmers can't use it the
way they use pointers).

As a side note, a reference must refer to some object at all times, but a pointer can point to NULL. In this
way, references can be more efficient when you know that you'll always have an object to point to,
because you don't have to check against NULL:
void func(MyClass &obj) 
{ 
obj.Foo(); 
}
Is better than:
void func(MyClass *obj)
{ 
if (obj) obj->Foo(); 
}

14.> How do you do dynamic memory allocation in C applications? List advantages and disadvantages of
dynamic memory allocation vs. static memory allocation.

Answer:

  
In C, malloc, calloc and realloc are used to allocate memory dynamically. In C++, new(), is usually used to
allocate objects. Some advantages and disadvantages of dynamic memory allocation are:

Advantages:
• Memory is allocated on an as-needed basis. This helps remove the inefficiencies inherent to static
memory allocation (when the amount of memory needed is not known at compile time and one has to
make a guess).
Disadvantages:
• Dynamic memory allocation is slower than static memory allocation. This is because dynamic memory
allocation happens in the heap area.
• Dynamic memory needs to be carefully deleted after use. They are created in non-contiguous area of
memory segment.
• Dynamic memory allocation causes contention between threads, so it degrades performance when it
happens in a thread.
• Memory fragmentation.

15.> How do I write code that reads data at memory location specified by segment and
offset?
Answer: 

Use peekb( ) function. This function returns byte(s) read from specific segment and
offset locations in memory. The following program illustrates use of this function. In this
program from VDU memory we have read characters and its attributes of the first row.
The information stored in file is then further read and displayed using peek( ) function.

main( )
{
char far *scr = 0xB8000000 ;
FILE *fp ;
int offset ;
char ch ;
if ( ( fp = fopen ( "scr.dat", "wb" ) ) == NULL )
{
printf ( "\nUnable to open file" ) ;
exit( ) ;
}
// reads and writes to file
for ( offset = 0 ; offset < 160 ; offset++ )
fprintf ( fp, "%c", peekb ( scr, offset ) ) ;
fclose ( fp ) ;
if ( ( fp = fopen ( "scr.dat", "rb" ) ) == NULL )
{
printf ( "\nUnable to open file" ) ;
exit( ) ;
}
// reads and writes to file
for ( offset = 0 ; offset < 160 ; offset++ )
{
fscanf ( fp, "%c", &ch ) ;
printf ( "%c", ch ) ;
}
fclose ( fp ) ;
}

16.> Why doesn't the following statement work?

char str[ ] = "Hello" ;

strcat ( str, '!' ) ;
Answer: 

The string function strcat( ) concatenates strings and not a character. The basic
difference between a string and a character is that a string is a collection of characters,
represented by an array of characters whereas a character is a single character. To
make the above statement work writes the statement as shown below:
strcat ( str, "!" ) ;

17.> What will be the output of the following code?

void main ()
{
   int i = 0 , a[3] ;
   a[i] = i++;
   printf (“%d",a[i]) ;
}

Answer: 

The output for the above code would be a garbage value. In the statement a[i] = i++; the
value of the variable i would get assigned first to a[i] i.e. a[0] and then the value of i
would get incremented by 1. Since a[i] i.e. a[1] has not been initialized, a[i] will have a
garbage value.

18.> Problem: Write code for doing a breadth first search in a Tree data structure.

Solution: Breadth first search inspects items one level at a time starting with the root node. This is unlike
the Depth First Search where the nodes in the left most branch are visited until there are no more nodes
and then backtracks.

The problem with implementing a breadth first search is that we have to remember the list of nodes at the
same level before moving to the next level. This can be achieved by using a queue data structure. See
this post on details of how to implement a Queue using an array. Every time we visit a node, we inspect
the data contained in the node before Enqueueing both children to the Queue. If the node contains the
data we were searching for we return the pointer to that node. 
//Breadth First Search (BFS) method searches the tree one level at a time

Node * Breadth-First-Search(Node *root, int searchValue)

{
Queue queue;
queue.Enqueue(root);
Node * currentNode;
while(currentNode = queue.Dequeue())
{
if(currentNode->data == searchVal)
 return currentNode;

queue.Enqueue(currentNode->left);
queue.Enqueue(currentNode->right);
}
}

19.> Problem: Implement a queue using an Array. Make efficient use of the space in the array. 

Solution: Queue is a data structure that supports Enqueue and Dequeue methods. The Enqueue method
adds an item to the end of the list and Dequeue method removes an item from the beginning of the list.
This means that the Queue is a FIFO (First In First Out) data structure. Theoretically speaking a Queue
doesn't have a fixed size. It grows as items are added to the end of the list. The implementation below
has a fixed sized determined at the time of instantiating the Queue object. Ideally, the array should be
reallocated to accommodate more items. The implementations makes use of the space efficiently by
reusing space that is released when items are dequeued. 

/************ Queue.h *********************/

// Queue class implements the Queue ADT(abstract data type) or Abstract Data
Structure
// using an array as the underlying data structure
class Queue
{
private:
int *itemsArray; // array used for storing items in the queue
int startIndex; // index in the array where the queue starts
int size; // size of the array holding the queue
int count; // number of items in queue

public:
Queue(int size);
~Queue();
void Enqueue(int i);
int Dequeue();
int GetCount();
void Print();
};
/************ Queue.cpp *********************/
#include "stdafx.h"
#include "malloc.h"
#include "Queue.h"

Queue::Queue(int size)
{
this->size = size;
itemsArray = (int *)malloc(sizeof(int) * size);
startIndex = 0;
count = 0;
}
20.> What is the difference between an external iterator and an internal iterator? Describe an advantage
of an external iterator.

Ans : Answer: An internal iterator is implemented with member functions of the class that has items to
step through. .An external iterator is implemented as a separate class that can be "attach" to the object
that has items to step through. .An external iterator has the advantage that many difference iterators can
be active simultaneously on the same object.

21. > Which recursive sorting technique always makes recursive calls to sort subarrays that are about half
size of the original array?

Ans : Answer: Mergesort always makes recursive calls to sort subarrays that are about half size of the original array,
resulting in O(n log n) time.

22.>