C++ Interview Faq - Answered

Is Tree Balanced - Hint: find the depth of a tree (max depth) and see if it is the minimum depth.

BOOL IsTreeBalanced(Node* Root) {         if(Root == NULL)                return FALSE;                 return ((maxDepth(Root) - minDepth(Root)) <= 1); } int maxDepth(Node* Root) {         (Root == NULL) ? 0: max(maxDepth(Root->left), maxDepth(Root->right)) + 1; } int minDepth(Node* Root) {         (Root == NULL) ? 0: min(minDepth(Root->left), minDepth(Root->right)) + 1; }

Delete a Tree.

void DeleteTree(Node* Root) {     if(Root == NULL)                return;                 DeleteTree(Root->left);         DeleteTree(Root->Right);              delete Root; }

Size of a Tree.

int TreeSize(Node* Root) {         if(Root == NULL)                return 0;                 return TreeSize(Root->left) + TreeSize(Root->right) + 1; }

Copy the Given Linked List.

void CopyList(Node* Source, Node **Destination) {         if(Source == NULL)                return;                 //we can also delete if it is not NULL and then allocate         if(*Destination == NULL)                *Destination = (Node*) malloc(sizeof(Node));                 (*Destination)->Data = Source->Data;         (*Destination)->next = Source->next;                 CopyList(Source->next, &(*Destination)->next); }

Compare Two Given Linked Lists

BOOL compareList(Node* First, Node* Second) {         if((First == NULL) && (Second == NULL))                return TRUE;         //we might have to write Length function for a Given List         else if((First == NULL) || (Second == NULL)                || (Length(First) != Length(Second)) )                return FALSE;         else         {                do                {                        if(First->Data != Second->Data )                        {                               return FALSE;                        }                }                //Or is only needed when we dont check above for length equality                while(First->Next != NULL || Second->Next != NULL);                return TRUE;           } }

Is Given Linked List is Cyclic ?

BOOL IsCyclicList(Node* Root) {         if(Root == NULL)                return FALSE; // or may be a throw                        Node    *slow, *fast;         slow = fast = Root;                 while (true)         {                if((!fast) || (!fast->next)                        return FALSE;                elseif((slow == fast) || (slow == fast->next))                        return TRUE                else                {                        slow = slow->next;                        fast = fast->next->next;                }         } }

Find the Middle Element in a Given Linked List ?

void FindMiddle(Node* Root) {         if(Root == NULL)                return FALSE; // or may be a throw                        Node    *slow, *fast;         slow = fast = Root;         int count = 0;                 while (fast != NULL || fast->next != NULL)         {                slow = slow->next;                fast = fas->next->next;                count ++;         }         (fast == NULL) ? /*even list*/: slow; }

Reverse a Single Linked List ?

void ReverseList(Node* Root) {         Node *New  = NULL;         while(Root != NULL)         {                Node* Next = Root->next;                Root  = Root->next;                               Next->next = New;                New = Next;            } }

Reverse a Double Linked List ?

void ReverseDList(Node *Root) {         while(Root)         {                Node* temp = Root->next;                Root->next = Root->previous;                Root->previous = temp;                if(temp == NULL)                        break;                Root = temp;         }         return Root; }

Implement Breadth First Search Algorithm for a given Binary Tree? (Hint: Use Queues)

Node* BFS(Node* Root, int searchVal) {         if (Root == NULL)                return;         Queue myQ;         myQ.Enqueue(Root);                 Node* current;         while (current = myQ.Dequeue())         {                if(current == NULL)                        break;                if(current->data == searchVal)                        return current;                myQ.Enqueue(Root->GetLeft());                myQ.Enqueue(Root->GetRight());         }         return NULL; }

Find Nth Node from Backwards in a Given List.

Node* FindNthFromBack(Node* Root, int n) {         Node *pNthNode, *pCurrent;                 while (n > 0)         {                      pCurrent = pCurrent->next;                n--;         }                 while (pCurrent)         {                pCurrent = pCurrent->next;                pNthNode = pNthNode->next;         }                 return pNthNode; }

Please let me know if you have more Questions that you want me to Answer… J