SDE - 1

Iterative Inorder Traversal (Using Stack ) :
1) Create an empty stack S.
2) Initialize current node as root.
3) Push the current node to S and set root=root->left until root is NULL
4) If root is NULL and stack is not empty then 
a) Pop the top item from stack.
b) Print the popped item, set root = root->right 
c) Go to step 3.
5) If root is NULL and stack is empty then we are done.

Time Complexity : O(n)
Space Complexity : O(n)

Recursive Inorder Traversal :
1) Initialise a global vector "answer" which will store the final inorder traversal of our BST
2) Create a recursive function(say void Inorder(TreeNode*root)) passing the root node as its initial paramter.
3) Base Case : If we encounter a NULL node i.e. root==NULL , then simply return from the function
4)Traverse the left subtree, i.e., call Inorder(root->left)
5)Visit the root. i.e. , push root->val into ans.
6)Traverse the right subtree, i.e., call Inorder(root->right)

Time Complexity : O(n)
Space Complexity : O(n)

Iterative(Without using stack):
1) Initialize three pointers prev as NULL, curr as head and next as NULL.

2) Iterate through the linked list. In loop, do following. 
// Before changing next of current, 
// store next node 
next = curr->next
// Now change next of current 
// This is where actual reversing happens 
curr->next = prev 
// Move prev and curr one step forward 
prev = curr 
curr = next

3)Finally the prev pointer contains our head , i,e. ,head=prev .

TC : O(n)
SC: O(1)


Recursive:
1) Divide the list in two parts - first node and rest of the linked list.
2) Call reverse for the rest of the linked list. 
3) Link rest to first.
4) Fix head pointer

TC:O(n)
SC:O(n)

Iterative(Using Stack):
1) Store the nodes(values and address) in the stack until all the values are entered.
2) Once all entries are done, Update the Head pointer to the last location(i.e the last value).
3) Start popping the nodes(value and address) and store them in the same order until the stack is empty.
4) Update the next pointer of last Node in the stack by NULL.

TC: O(n)
SC:O(n)

Union : 
1) Initialize an empty hash set or hash map mp;
2) Iterate through the first array and put every element of the first array in the set mp.
3) Repeat the process for the second array.
4) Print the set mp.

Intersection:
1) Initialize an empty set mp.
2) Iterate through the first array and put every element of the first array in the set mp.
3) For every element x of the second array, do the following :
Search x in the set mp. If x is present, then print it. 

Time complexity : O(m+n) under the assumption that hash table search and insert operations take O(1) time.
Space complexity : O(m+n) in case of Union and O(min(m,n)) in case of Intersection