### BFS vs DFS (Breadth First Search vs Depth First Search)

Breadth First Search (BFS) Depth First Search (DFS)
Data Structure Used Queue Stack
Traversal Level order Traversal

Inorder Traversal (Left-Root-Right)

Preorder Traversal (Root-Left-Right)

Postorder Traversal (Left-Right-Root)

Starts visiting nodes from root or leaves

Root

Leaves

When to use

If our problem is to search something that is more likely to closer to root. If the target node is close to a leaf, we would prefer DFS
Approach Iterative Reccursive
Shortes Path Problem BFS is more efficient than DFS. DFS is not recommended as it will start traversing from a leaf node.
Implementation

//Search element with integer data
private GraphNode SearchBFS(GraphNode node, int valueToCheck)
{
//validate node
if (node == null)
{
return node;
}

Queue<GraphNode> nodesToProcess = new Queue<GraphNode>();
//mark as visited
node.MarkAsVisited = true;
nodesToProcess.Enqueue(node);

while (nodesToProcess.Count > 0)
{
GraphNode currentNode = nodesToProcess.Dequeue();

//visit node
if (currentNode.Value == valueToCheck)
{
return currentNode;
}

{
{
}
}
currentNode = nodesToProcess.Dequeue();
}

return null;
}

//Search element with integer data
//Pre-Order traversal
private GraphNode SearchDFS(GraphNode node, int valueToCheck)
{
//validate node
if (node == null)
{
return node;
}

//visit node
if (node.Value == valueToCheck)
{
return node;
}

//mark as visited
node.MarkAsVisited = true;

{
{
//Search reccursively starting with first adjucent node
}
}

return null;
}

Space Complexity Extra Space required for Level Order Traversal is O(w) where w is a maximum width of Binary Tree.  Extra Space required for Depth First Traversals is O(h) where h is a maximum height of Binary Tree.
Search the entire tree

Depth First Search is commonly used when you need to search the entire tree.

Lower memory requirements   DFS is that it has much lower memory requirements than BFS because it’s not necessary to store all of the child pointers at each level.
Example Finding the neighbor nodes in the peer to peer networks like Bit Torrent, GPS systems to find nearby locations, social networking sites to find people in the specified distance and things like that.

Games like Chess, tic-tac-toe when you are deciding what move to make, you can mentally imagine a move, then your opponent’s possible responses, then your responses, and so on. You can decide what to do by seeing which move leads to the best outcome.

Searching files in file system.

Temporary Storage at time of exicution BFS requires you store the entire 'frontier' DFS only requires you store the list of parent nodes of the current element.
If the tree is very deep and solutions are rare If the tree is very deep and solutions are rare, depth-first search (DFS) might take an extremely long time, but BFS could be faster.
If solutions are frequent but located deep   If solutions are frequent but located deep in the tree, BFS could be impractical.
If the tree is very wide    If the tree is very wide, a BFS might need too much memory, so it might be completely impractical.
When the depth of the tree can vary Breadth First Search is generally the best approach when the depth of the tree can vary, and you only need to search part of the tree for a solution.

### Merge Sort vs Quick Sort

Merge Sort Quick Sort
Implementation

void MeargeSort(int[] arr)
{
int[] helper = new int[arr.Length];
MergeSort(arr, helper, 0, arr.Length);
}

void MergeSort(int[] arr, int[] helper, int low, int high)
{
if (low < high)
{
int middle = (low + high) / 2;
MergeSort(arr, helper, low, middle);
MergeSort(arr, helper, low, middle);
Merge(arr, helper, low, middle, high);
}
}

void Merge(int[] arr, int[] helper, int low, int middle, int high)
{
//Copy both halves into a helper array
for (int i=low; i<=high; i++)
{
helper[i] = arr[i];
}

int helperLeft = low;
int helperRight = middle + 1;
int current = low;
/*
Iterate through helper arry. Compare the left and riht half, Copying back
the smaller element from the two halves into the original array.
*/
while (helperLeft<= middle && helperRight<= high)
{
if (helper[helperLeft]<= helper[helperRight]) {
arr[current] = helper[helperLeft];
helperLeft++;
}
//If right element is small than left element
else
{
arr[current] = helper[helperRight];
helperRight++;
}
current++;
}

//Copy the rest of the left side of the arry inot the target array
int remaining = middle - helperLeft;
for (int i=0; i<= remaining; i++)
{
arr[current + i] = helper[helperLeft + i];
}
}

void QuickSort(int[] arr, int left, int right)
{
int index = QuickSortPartition(arr, left, right);
//Sort left half
if (left < index - 1)
{
QuickSort(arr, left, index - 1);
}
//Sort right half
if (index < right)
{
QuickSort(arr, index, right);
}

}

int QuickSortPartition(int[] arr, int left, int right)
{
//Pick Pivote Point
int pivoteValue = arr[(left + right) / 2];
while (left <= right)
{
//Find element on left that should be on right
while (arr[left] < pivoteValue) left++;
//Find element on right that should be on left
while (arr[left] < pivoteValue) left++;
//Swap elements, and move left and right indices
if (left < right)
{
//swaps elements Swap(arr, left, right);
arr.Swap(left, right);
left++;
right--;
}
}
return left;
}

Time Complexity Worst Case

O(N Log N), where N is the size of the structure (e.g. array).

O(N2), where N is the size of the data structure (e.g. array).

The worst case occurs when the array is reverse sorted.

Time Complexity Average Case

O(N Log N), where N is the size of the structure (e.g. array).

O(N Log N), where N is the size of the structure (e.g. array).

Works well when the data structure (e.g. array) is randomized.

Space Complexity

Depends.

Merge sort requires O(N) extra storage, where N is the size of the structure (e.g. array).

Constant

On arrays, merge sort requires O(n) space; on linked lists, merge sort requires constant space Randomly picking a pivot value (or shuffling the array prior to sorting) can help avoid worst-case scenarios such as a perfectly sorted array.
Preferred Data structure Linked List Array
Cache Friendly   Quick Sort is also a cache friendly sorting algorithm as it has good locality of reference when used for arrays.