Data structures

Question : Write a function to test if two binary trees are equal. The trees are equal only if the values are equal and also the structures are equal. Equal trees       89                                89   12      100                    12       100 2                                 2 Not equal trees         89                          ...

Qn: Write a function to swap the adjacent nodes of a singly linked list.i.e. If the list has nodes as 1,2,3,4,5,6,7,8, after swapping, the list should be 2,1,4,3,6,5,8,7 Image from: https://tekmarathon.com Though the question looks simple enough, it is tricky because you don't just swap the pointers. You need to take care of links as well. So let us try to understand how to go about it. Take two adjacent nodes p1 and p2 Let prevnode be previous node of p1 Now link prevnode to p2 Link p2 to p1 Link p1 to next node of p2 So the code will be prevnode -> next = p2; p1 -> next = p2 -> next; p2 -> next = p1; But what about the start node or head? head node does not have previous node If we swap head with second node, modified head should be sent back to caller  To take care of swapping first and second nodes, we can write p1 = head; p2 = head -> next; p1 -> next = p2 -> next; p2 -> next = p1; head = p2;  Now we are...

Sorting a linked list is much more complex than sorting an array. Because you need to be wary of links at each step and update them. The most convenient ways of sorting a linked list is insertion sort, where in you remove one node at a time from list and insert them to the sorted list in correct position. But merge sorting a linked list uses another approach. It splits the list into two halves, sorts them recursively and then merges them maintaining ascending order of key values. So the three basic parts of this approach are Splitting the list into two halves of equal length Sorting these halves Merging the halves Step 2 is in fact not needed if the list has only one node. One node is sorted. Hence the merge sort algorithm is If the list has more than one node Splitting the list into two halves of equal length Sorting these halves recursively using steps 2 to 4 Merging the halves   Split the list into halves We have seen in this post how to find the m...

How do you merge two binary search trees? I googled about the solutions. Most solutions told me to convert both trees into linked lists. Merge the lists. Then create a tree from the elements of the list. But why lists? Why can't we store the elements in an array? Because if the data of the tree is larger - not just integer keys, array manipulation becomes difficult. But again, we need not convert both the trees into lists. We can convert one tree into list - a doubly linked list. Then insert the elements of this list into the other tree. I tried this approach. To convert a tree into a sorted doubly linked list Create a doubly linked list. Let the prev and next links of nodes in this list be called left and right respectively. This way we can directly use the binary tree nodes in the list. Use a static variable previousnode  call the function recursively for left child of current node. link current node to the previousnode set next pointer of previousnode to curre...

A doubly linked list has two pointers in each node. Pointer to previous node and pointer to next node. We have seen that reversing a singly linked list is not so easy. Because you do not have previous pointer. Since our DLL has previous pointers, its reversal must be easy. I wrote a program earlier similar to SLL reversal- taking 3 nodes at a time and reversing links of two adjacent nodes. But I came across a better solution. Just swap the previous link and next link for each node. NODEPTR reverse_list (NODEPTR head ) { NODEPTR temp = head; NODEPTR t1; while (temp) { //swap links t1 = temp -> prev; temp -> prev = temp -> next; temp -> next = t1; //move to next node temp = temp -> prev; } if (t1 != NULL ) head = t1 -> prev; return head; } If there was only one node in the list, then t1 will be NULL and head=t1->prev will crash the program. So verify that t1 is not NULL....

Now let us write a function to count the number of nodes in a singly linked list. This one is pretty simple. traverse the list from first node increment count after each node count at the end of traversal is the number of nodes int get_count (NODEPTR temp) { int c = 0 ; while (temp) { c ++ ; temp = temp -> next; } return c; } The function starts with head node and loops till temp becomes NULL. Please remember that NULL has a numerical value of 0 and 0 is false and the condition ( temp ) is as good as saying ( temp!=NULL ). How about a recursive function for the same? int get_count_recursive (NODEPTR temp) { if (temp != NULL ) { return get_count_recursive(temp -> next) +1 ; } } Time to write the driver program for this function #include<stdio.h> #include<stdlib.h> struct node { int n; struct node * next; }; typedef struct node * NODEPTR; NODEPTR...

Question : Implement a stack which finds the minimum of elements in the stack. All the three functions push(), pop() and findmin() must have time complexity of O(1) This is one of the common questions asked in interviews. The problem is finding minimum requires you to traverse through the stack, which is not possible without popping elements. So you can pop elements, find minimum and then push the elements back. But the requirement says that findmin() function must have a constant complexity - O(1). You can achieve this with the help of one more stack, to store minimum values. Let us call this minstack. This is how the operations will work push -  push a value to stack compare the value with top of minstack if value is smaller than minstack top element push it to minstack if not push minstack top element again to minstack pop  pop a value from stack pop a value from minstack findmin get the value from minstack without popping it (peek) ...