# DS Overlapping Problem

1. Tree and Stack –  Iterative Postorder Traversal | Set 1 (Using Two Stacks) and  Iterative Postorder Traversal | Set 2 (Using One Stack)  and Check if a given array can represent Preorder Traversal of Binary Search Tree
2. Tree and Stack – Print ancestors of a given binary tree node without recursion
3. Tree and Deque – Sliding Window Maximum (Maximum of all subarrays of size k)   – Given an array and an integer k, find the maximum for each and every contiguous subarray of size k.
4. Hashing and Tree – Print a Binary Tree in Vertical Order
5. Hashing and Tree – Advantages of BST over Hash Table
6. Tree and Hash – Given an unsorted array with repetitions, the task is to group multiple occurrence of individual elements. The grouping should happen in a way that the order of first occurrences of all elements is maintained.
7. Tree and Queue – Iterative Method to find Height of Binary Tree
8. Tree and Linked List – Construct Complete Binary Tree from its Linked List Representation
9. Convert a given Binary Tree to Doubly Linked List | Set
10. [Done] ***Queue and Stack – Code – Implement Queue using Stacks (using 2 stack)
We create two stack, s1 and s2. s1 is the one where all queue operation happen. When we need to dequeue, we move all s1 item to s2 and pop from s2, until s2 is empty. This will have a FIFO effect. Now we keep popping from s2(for every dequeue op) until it’s empty and meanwhile all push op will be in s1.  When s2 is empty and another dequeue op is needed we pop all s1 to s2.
11. Graph and Stack – Iterative Depth First Traversal of Graph
12. Stack/Queue and Tree – Algo to invert a Binary Tree
13. Stack and Queue – Implement a stack using single queue
14. [Done] ***Stack and Queue – Implement Stack using Queues – two approach – check here
15. [Done] * Stack and Linked List – Stack Implementation using Linked List – Simple.
16. Sort and Doubly Linked List – Quick Sort and Merge
17. Stack and Doubly Linked List – Design a stack with operations on middle element. How to implement a stack which will support following operations in O(1) time complexity – push(), pop(), findMiddle(), deleteMiddle();
18. [Done] Queue and Linked List – How to use Queue with Linked List  Implementation Code. This is pretty straight forward. We just need to create a Linked List class will be used as out node. In our Queue class we will need to maintain front and rear(which will be reference to the Linked List Node created to hold). Rest we just need to keep maintaining these front and end as and when we queue and dequeue nodes from the queue. Handle the case of empty queue(when both front and rear are null).
19. *** Linked List and Sorting – Sort a Linked List using Merge Sort
20. Tree and Linked List – Tree to Linked List – Byte-by-byte
21. [Done] Linked List and Hashing – Union and Intersection of two Linked Lists
22. Tree and Queue – Check whether a given Binary Tree is Complete or not
23. [Done] Implement Stack using Queue –
Using One Queue  – when we queue an element to the queue we dequeue all the other element one by one and enqueue them, remove the element and enqueue it and then do the same with the next element. This happens in a loop size -1 time, this will cause the last element added to get to the front of the queue.
We do this for every element that’s added to the queue. So the pop operation will pop the last element added, LIFO like a stack.
Using Two Queue  –  Idea is to push elements into the Queue “mainQueue” and while popping element, pop all elements except the last element one by one from “mainQueue” to temporary Queue “tempQueue”, return the last element and initialize “mainQueue” with “tempQueue”.
One small but impactful change we do is, while copying tempQueue to mainQueue, we do not actually copy the data but initialize mainQueue = tempQueue and reinitialize the tempQueue. Basically renaming temp to main and creating a new temp.
mainQueue = tempQueue;