<?xml version="1.0" encoding="UTF-8"?>
<rss version="2.0" xmlns:atom="http://www.w3.org/2005/Atom" xmlns:dc="http://purl.org/dc/elements/1.1/">
  <channel>
    <title>Forem: Min Tu</title>
    <description>The latest articles on Forem by Min Tu (@dispensableart).</description>
    <link>https://forem.com/dispensableart</link>
    <image>
      <url>https://media2.dev.to/dynamic/image/width=90,height=90,fit=cover,gravity=auto,format=auto/https:%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Fuser%2Fprofile_image%2F1495734%2F1a48b5b5-05e3-48f5-850d-47a31b676b1d.png</url>
      <title>Forem: Min Tu</title>
      <link>https://forem.com/dispensableart</link>
    </image>
    <atom:link rel="self" type="application/rss+xml" href="https://forem.com/feed/dispensableart"/>
    <language>en</language>
    <item>
      <title>Algo Basics 101: Recursion Review</title>
      <dc:creator>Min Tu</dc:creator>
      <pubDate>Wed, 15 May 2024 02:39:16 +0000</pubDate>
      <link>https://forem.com/dispensableart/algo-basics-101-recursion-review-3ji</link>
      <guid>https://forem.com/dispensableart/algo-basics-101-recursion-review-3ji</guid>
      <description>&lt;p&gt;Recursion is when you define something in terms of itself, or simply it is a function that refers to itself inside of the function. It is a function that calls on itself inside itself.&lt;/p&gt;

&lt;p&gt;Recursion is really good for tasks that have repeated subtasks to do. Like when we want to look through every folder and its subfolders or traversing nested objects.&lt;/p&gt;

&lt;p&gt;This concept is used heavily in sorting algorithms and searching algorithms, such as when we traverse a tree.&lt;/p&gt;

&lt;p&gt;Stack Overflow&lt;br&gt;
When a call stack is overflowing with function calls, then that is a stack overflow. Think of it like if each function is like some amount of water and if you keep adding that amount of water to a cup, then the water overflows from the cup.&lt;/p&gt;

&lt;p&gt;In this case we run out of memory if we keep putting too many stacks in the call stack.&lt;/p&gt;

&lt;p&gt;Recursion’s big issue is having an infinite call loop allowing it to go on forever if there is no way to stop this recursive call.&lt;/p&gt;

&lt;p&gt;Interview Question: What is a problem with recursion?&lt;/p&gt;

&lt;p&gt;Answer: The computer needs to allocate memory to remember things so a stack overflow can occur when we have recursion and there is no way to stop the recursive call (if you have no base case). Basically the computer runs out of memory to store all of your function calls in its call stack.&lt;/p&gt;

&lt;p&gt;Anatomy of Recursion&lt;br&gt;
Every recursive function needs a base case or a stopping point where the function is no longer calling on itself.&lt;/p&gt;

&lt;p&gt;It’s like the point where you finally unravel the entire ball of yarn you’ve spun by repeatedly calling the function (spinning the yarn into a ball I guess). Think of the base case like the string you pull to finally unravel a huge complicated knot.&lt;/p&gt;

&lt;p&gt;In the case of getting all the items in a folder and its subfolders, our base case would be telling the program to stop when there are no longer any more folders in the subfolder.&lt;/p&gt;

&lt;p&gt;Recursive functions have two paths:&lt;/p&gt;

&lt;p&gt;recursive case: this is the case where we call the function itself again and run it&lt;br&gt;
base case: this is the case where we say stop calling the function&lt;br&gt;
In this example, there will be an undefined return:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;let counter = 0;
function inception(){
    if(counter &amp;gt; 3){
       return 'done!';
    }
    counter++;
    inception();
}
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;But why does it return undefined? This is because this is essentially what we’re doing:&lt;/p&gt;

&lt;p&gt;inception(inception(inception(inception(inception()))))&lt;/p&gt;

&lt;p&gt;So now it goes like this:&lt;/p&gt;

&lt;p&gt;inception(inception(inception(inception(‘done!’))))&lt;/p&gt;

&lt;p&gt;Now on the inside we have inception(‘done!’) which doesn’t actually return anything. When a function doesn’t return anything, it just returns undefined. So we have to tell the function the return ‘done!’ and bubble it up.&lt;/p&gt;

&lt;p&gt;You want to make sure that you always return so the value you want gets bubbled all the way to the top.&lt;/p&gt;

&lt;p&gt;In this case, the correct way to write this recursive function so that it returns ‘done!’.&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;let counter = 0;
function inception(){
    if(counter &amp;gt; 3){
      return 'done!';
    }
    counter++;
    return inception(); // we have to add this return statement to bubble up 'done!'
}
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;If you don’t do this, the result will never be bubbled up.&lt;/p&gt;

&lt;p&gt;Here are the steps for writing a recursive function:&lt;/p&gt;

&lt;p&gt;Identify the base case.&lt;br&gt;
Identify the recursive case.&lt;br&gt;
Get closer and closer and return when needed or when you reach your desired base case. Usually you have two returns, one for the base case and one for the recursive case, the latter of which to bubble up the return from the base case.&lt;br&gt;
Conclusion&lt;br&gt;
Identifying the base case will allow you to write recursive functions a lot easier. I wanted to write this quick review and guide so that people can always refresh on the basics.&lt;/p&gt;

&lt;p&gt;Never forget to review your basics.&lt;/p&gt;

&lt;p&gt;Happy coding and happy new year!&lt;/p&gt;

</description>
      <category>recursion</category>
      <category>datastructures</category>
    </item>
    <item>
      <title>Implementing BFS and DFS in JavaScript</title>
      <dc:creator>Min Tu</dc:creator>
      <pubDate>Wed, 15 May 2024 02:33:14 +0000</pubDate>
      <link>https://forem.com/dispensableart/implementing-bfs-and-dfs-in-javascript-1f0e</link>
      <guid>https://forem.com/dispensableart/implementing-bfs-and-dfs-in-javascript-1f0e</guid>
      <description>&lt;h2&gt;
  
  
  BFS (Breath First Search) Introduction
&lt;/h2&gt;

&lt;p&gt;This search basically goes from left to right at every level of the tree. So if you had the following tree:&lt;/p&gt;

&lt;p&gt;&lt;a href="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F6fhjr1lezga9ymhdgklj.png" class="article-body-image-wrapper"&gt;&lt;img src="https://media.dev.to/cdn-cgi/image/width=800%2Cheight=%2Cfit=scale-down%2Cgravity=auto%2Cformat=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2F6fhjr1lezga9ymhdgklj.png" alt="Image description" width="623" height="340"&gt;&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;A breadth first search would run through this tree in this order starting from the top level:&lt;/p&gt;

&lt;p&gt;9 → 6 → 12 → 1 → 4 → 34 → 45&lt;/p&gt;

&lt;p&gt;See how it goes left to right at each level going from the top level and then down a level and then going left and right again until it reaches the bottom level? It is essentially searching every node by searching every node at each level.&lt;/p&gt;

&lt;p&gt;BFS uses additional memory because it is necessary to track all the nodes on a given level while searching that level, this means that we need to track every node and its children in order.&lt;/p&gt;

&lt;p&gt;DFS (Depth First Search) Introduction&lt;br&gt;
Depth first search (DFS) follows one branch of the tree down as many levels as possible until the target node is found or the end of the branch is reached.&lt;/p&gt;

&lt;p&gt;When the search can’t go on any further, it goes back up to the nearest ancestor (parent node) with an unexplored child (child node that has not be gone down) and then continues down that child’s branch until it can’t anymore.&lt;/p&gt;

&lt;p&gt;So let’s go back to this example:&lt;/p&gt;

&lt;p&gt;For DFS we prioritize going down as deep as possible, so we start at the root node, 9. Then we go to 6 and then 1. But then we see that there are no more children after 1 (it is a leaf node). So then we go back up to 6 since it is the nearest ancestor that still has unexplored child nodes and from there we go to its unexplored child which is the node with the value of 4.&lt;/p&gt;

&lt;p&gt;We then see that there is no more children after 4 so we go back up to 6, see that 6 no longer has any child nodes that are unexplored, so we go back up to 9 and see that we have unexplored child nodes, so we go to the unexplored child node which is 12. Then we go to 34. We see that 34 has no children (is a leaf node), so we go back up to 12, see that it has an unexplored child node of 45 and then we go to 45.&lt;/p&gt;

&lt;p&gt;Does that make sense? We go as far down as we can first before checking every other vertical “branch”.&lt;/p&gt;

&lt;p&gt;9 → 6 → 1 → 4 → 12 → 34 → 45&lt;/p&gt;

&lt;p&gt;DFS has a lower memory requirement than BFS because it’s not necessary to store all the child pointers at each level.&lt;/p&gt;

&lt;p&gt;BFS vs DFS&lt;br&gt;
BFS is like checking everything on one floor of a building before going to the next floor.&lt;/p&gt;

&lt;p&gt;DFS is like going all the way down and then checking if there are any stairs you forgot to go down and checking down those.&lt;/p&gt;

&lt;p&gt;In interviews, you’ll be asked about what type of traversal to do and usually you’ll have to answer BFS or DFS.&lt;/p&gt;

&lt;p&gt;All traversals are O(n) so for both BFS and DFS, the time complexity is O(n).&lt;/p&gt;

&lt;p&gt;The order is the thing that matters when it comes to BFS and DFS.&lt;/p&gt;

&lt;p&gt;Extra Resources for BFS vs. DFS&lt;br&gt;
&lt;a href="https://stackoverflow.com/questions/9844193/what-is-the-time-and-space-complexity-of-a-breadth-first-and-depth-first-tree-tr"&gt;https://stackoverflow.com/questions/9844193/what-is-the-time-and-space-complexity-of-a-breadth-first-and-depth-first-tree-tr&lt;/a&gt;&lt;/p&gt;

&lt;p&gt;Exercise: BFS vs DFS&lt;br&gt;
If you know a solution is not far from the root of the tree: BFS (breadth first search)&lt;br&gt;
If the tree is very deep and solutions are rare: BFS (breadth first search) this is because the tree is already very deep meaning that DFS would took a long time just to search even one branch and because the solution is rare it will take a long time per branch (BDS however has memory concerns)&lt;br&gt;
If the tree is very wide: DFS (depth first search) — this is because if the tree is wide and a BFS is very memory-intensive then storing all the children for each node will take up a lot of memory&lt;br&gt;
If solutions are frequent but located deep in the tree: DFS (depth first search)&lt;br&gt;
Determining whether a path exists between two nodes: DFS (depth first search)&lt;br&gt;
Finding the shortest path: BFS (breadth first search)&lt;br&gt;
breadthFirstSearch()&lt;br&gt;
We have to keep track of every child node, so that we can go back and visit each of the children nodes. This is why BFS is so memory-intensive.&lt;/p&gt;

&lt;p&gt;Let’s implement a breadth first search (BFS) on the example tree from above:&lt;/p&gt;

&lt;p&gt;breadthFirstSearch(){&lt;br&gt;
//the currentNode starts at the head or the root node to begin its search&lt;br&gt;
let currentNode = this.root;&lt;br&gt;
//the list is an array where we store the values of the nodes that we will return&lt;br&gt;
let list = [ ];&lt;br&gt;
//the queue array below will store all of the child nodes (stores the nodes, not the&lt;br&gt;
value of the nodes which are stored in list, we need to store the nodes so that we can&lt;br&gt;
reference the left and right properties of the nodes to get the child nodes) of the level we are on, so this is where we run into possible memory and storage issues because we might have to store too many child nodes&lt;br&gt;
let queue = [ ];&lt;br&gt;
//we first push the root node into the queue array because that will be the first node&lt;br&gt;
we check and the first node we will be extracting child nodes from&lt;br&gt;
queue.push(currentNode);&lt;br&gt;
//the while loop keeps running until the queue array is empty which means that there&lt;br&gt;
are no more children to explore&lt;br&gt;
while(queue.length &amp;gt; 0){&lt;br&gt;
//we set the currentNode to the first item in the queue array&lt;br&gt;
the shift() function removes and returns the first item in the array&lt;br&gt;
currentNode = queue.shift();&lt;br&gt;
//we then add the value of the currentNode to the list&lt;br&gt;
list.push(currentNode.value);&lt;br&gt;
//if the a child node exists to the left of the currentNode, we push that node to&lt;br&gt;
the queue array where we store nodes that we have to check for children&lt;br&gt;
if(currentNode.left){&lt;br&gt;
queue.push(currentNode.left);&lt;br&gt;
}&lt;br&gt;
//if the a child node exists to the right of the currentNode, we push that node&lt;br&gt;
to the queue array where we store nodes that we have to check for children&lt;br&gt;
if(currentNode.right){&lt;br&gt;
queue.push(currentNode.right);&lt;br&gt;
}&lt;br&gt;
}&lt;br&gt;
return list;&lt;br&gt;
};&lt;br&gt;
So to trace the code, we start with 9 as the currentNode. We push the currentNode into the queue array so the queue array current reads: [ {value: 9, this.left: 6, this.right: 12} ]&lt;/p&gt;

&lt;p&gt;Then we enter the while loop because the queue array is not empty. First we reach the set the currentNode equal to the first item in the queue array using shift(), which, as of now, only contains the root node of {value: 9, this.left: 6, this.right: 12}&lt;/p&gt;

&lt;p&gt;We then add the value of the currentNode into our list that we will return at the end.&lt;/p&gt;

&lt;p&gt;So because we used shift() we actually remove the first item from the array so as of now our queue array is temporarily empty with [ ] while we are in the while loop. By the time we reach the end of our first pass through the while loop, we will repopulate it as we see in the code below with the if statements.&lt;/p&gt;

&lt;p&gt;With the if statements, we first check if there is a left node, and we check if there is a left node on the currentNode, which is currently {value: 9, this.left: 6, this.right: 12}. There is a left node on currentNode so we push that node into the queue array, repopulating it. The queue array now contains [{value: 6, this.left: 1, this.right: 4}].&lt;/p&gt;

&lt;p&gt;Then with the next if statement, we check if there is a right node on the currentNode which is still set to the root node (NOTE: we only change the currentNode on the start of another pass through the while loop, so currently the root node is still the currentNode), {value: 9, this.left: 6, this.right: 12}. There is a right node on currentNode so we push that node into the queue array, adding to the array. The queue array now contains [{value: 6, this.left: 1, this.right: 4}, {value: 12, this.left: 34, this.right: 45}]&lt;/p&gt;

&lt;p&gt;The list array currently contains: [9]&lt;/p&gt;

&lt;p&gt;Upon another pass through the while loop, since the queue array is not empty, we then set the currentNode to the first item in the queue array with the shift method (remember this removes and returns the first item of the array we call shift on). We then add the value of the current node to the list array.&lt;/p&gt;

&lt;p&gt;So currently, the currentNode is {value: 6, this.left: 1, this.right: 4}&lt;/p&gt;

&lt;p&gt;The list array is [9, 6]&lt;/p&gt;

&lt;p&gt;And the queue array is [{value: 12, this.left: 34, this.right: 45}] since we removed the first item of the array and set it to currentNode&lt;/p&gt;

&lt;p&gt;We then check the left and right child nodes of the currentNode, {value: 6, this.left: 1, this.right: 4}, and then push them into the queue array, making it now:&lt;/p&gt;

&lt;p&gt;[{value: 12, this.left: 34, this.right: 45}, {value: 1, this.left: null, this.right: null}, {value: 4, this.left: null, this.right: null}]&lt;/p&gt;

&lt;p&gt;In the next pass through the while loop we will end up with the following by the end of the pass:&lt;/p&gt;

&lt;p&gt;The currentNode will be {value: 12, this.left: 34, this.right: 45}&lt;/p&gt;

&lt;p&gt;The list array will be [9, 6, 12]&lt;/p&gt;

&lt;p&gt;The queue array will be [{value: 1, this.left: null, this.right: null}, {value: 4, this.left: null, this.right: null}, {value: 34, this.left: null, this.right: null}, {value: 45, this.left: null, this.right: null}]&lt;/p&gt;

&lt;p&gt;Do you see how the queue array can be a huge drain on memory now? It can grow way too big if you have too many levels.&lt;/p&gt;

&lt;p&gt;DFS: InOrder, PreOrder, PostOrder&lt;br&gt;
There are three ways to implement depth first search (DFS):&lt;/p&gt;

&lt;p&gt;InOrder&lt;br&gt;
PreOrder&lt;br&gt;
PostOrder&lt;br&gt;
Let’s use this tree as an example (it is different than the heap we used in BFS):&lt;/p&gt;

&lt;p&gt;InOrder is where we use DFS to traverse a binary search tree and return it in order which means that the return has sorted every node value from least to greatest already within the InOrder’s return.&lt;/p&gt;

&lt;p&gt;PostOrder on example: [ 1, 4, 6, 9, 15, 20, 170 ]&lt;/p&gt;

&lt;p&gt;PreOrder is where we start at the root node and then keep going down one of its children till you can’t go any further down, goes back up to a node that still has children and then goes down that branch until it can’t anymore. PreOrder’s return is good because it makes it easier to recreate a tree because it is ordered that way for us.&lt;/p&gt;

&lt;p&gt;PostOrder on example: [ 9, 4, 1, 6, 20, 15, 170 ]&lt;/p&gt;

&lt;p&gt;PostOrder is where we go all the way down to the lowest level recording what’s there, and then recording the parent of those two children at the bottom level, traversing back up to reach another two leaf nodes at the bottom level, recording those two, then recording their parent, and so on and so forth. In this case, the children nodes are recorded before their parent nodes. This means that the root node would be the last thing in the array. It goes like [leaf node, leaf node, parent of leaf, leaf node, leaf node, other parent of leaf, parent of parent leaf node, other parent of other parent of leaf node, root node]&lt;/p&gt;

&lt;p&gt;PostOrder on example: [ 1, 6, 4, 15, 170, 20, 9 ]&lt;/p&gt;

&lt;p&gt;depthFirstSearch()&lt;br&gt;
Now let’s implement a depth first search (DFS). We will write one for InOrder, PreOrder, and PostOrder. So we would have the following (in our tree class that’s why there isn’t a function keyword):&lt;/p&gt;

&lt;p&gt;//we return a function in these and they are all recursive simply because of the nature of DFS. we once again must start at the root node and our empty array, or the list, will contain the values of our nodes&lt;br&gt;
DFSInOrder(){&lt;br&gt;
return traverseInOrder( this.root, [ ]);&lt;br&gt;
}&lt;br&gt;
DFSPostOrder(){&lt;br&gt;
return traversePostOrder( this.root, [ ]);&lt;br&gt;
}&lt;br&gt;
DFSPreOrder(){&lt;br&gt;
return traversePreOrder( this.root, [ ]);&lt;br&gt;
}&lt;br&gt;
//now down here we’ll write the functions we are returning in the above DFS’s&lt;br&gt;
//we want the list to have our node values in sorted order for InOrder DFS&lt;br&gt;
function traverseInOrder( node, list ){&lt;br&gt;
//this recursive case says, go all the way to the left until there are no more children&lt;br&gt;
//then add that leftmost value into the list&lt;br&gt;
if(node.left){&lt;br&gt;
traverseInOrder( node.left, list );&lt;br&gt;
}&lt;br&gt;
list.push(node.value);&lt;br&gt;
//we do the same to any right child, we only move onto checking for right children&lt;br&gt;
after checking for left so this ensures that we are not going from the root node directly&lt;br&gt;
to the rightmost node in the tree (see the logic written down below)&lt;br&gt;
if(node.right){&lt;br&gt;
traverseInOrder( node.right, list );&lt;br&gt;
}&lt;br&gt;
list.push(node.value);&lt;br&gt;
return list;&lt;br&gt;
}&lt;br&gt;
Because we are pushing our node values to the list only after we’ve verified the left nodes and traversed all the way down, the lowest numbers get put into the list first.&lt;/p&gt;

&lt;p&gt;Let’s word it out by using the above binary tree as an example. So we first traverse down to the leftmost node recursively. This is the node with the value of 1. Since there are no more left nodes, 1 gets pushed into the list array. Then the code checks for right nodes on 1. These do not exist since 1 is a leaf node. It returns the list array as [1] and now we will begin bubbling up the recursion.&lt;/p&gt;

&lt;p&gt;With the return of the recursion on the leftmost node of 1, we move up to the previous recursion which was called on its parent node of 4. Since in this part of the recursion we have already fulfilled the conditional in if(node.left), we then move onto the next line of code which is list.push(node.value) which means we then push 4 into the list array: [1, 4]&lt;/p&gt;

&lt;p&gt;After that, we move onto the next line of code which is the conditional of if(node.right), and this condition is fulfilled since 4 has a right node of value 6. So because this conditional is fulfilled, we run the code within the if statement which is another recursive function and it runs traverseInOrder() on the right child of 4 which is the node with the value of 6.&lt;/p&gt;

&lt;p&gt;Once 6 goes through its recursion, it will have no left nodes and no right nodes so it immediately gets its value pushed into the list array and then returned.&lt;/p&gt;

&lt;p&gt;This results in the following list array: [1, 4, 6]&lt;/p&gt;

&lt;p&gt;Then we go even further up our recursion and end up on the parent node of 4 which is the root node of 9. Since at this point in unraveling our recursion, we have already fulfilled the code in the conditional if(node.left), we move on to the next line of code, which pushes node.value into the list array so we add the value of 9 to it, resulting in: [1, 4, 6, 9]&lt;/p&gt;

&lt;p&gt;Then we move on to the next line of code, which checks for a right child on the 9, and it exists so we will have to execute the code within that if statement which is another recursion, that will be called on the right node of 9, so this is what will be executed: traverseInOrder( node with the value of 20, [1, 4, 6, 9] )&lt;/p&gt;

&lt;p&gt;Since we have to go down the entire line of traverseInOrder() again with the node with the value of 20, we will begin with checking to see if 20 has a left child and then keep on going to the left of that, so we will eventually end up at the node with the value of 15 and then push it into the list array, resulting in: [1, 4, 6, 9, 15]&lt;/p&gt;

&lt;p&gt;And so on and so forth. You can see now how this will resolve to [ 1, 4, 6, 9, 15, 20, 170 ]&lt;/p&gt;

&lt;p&gt;Now that we’ve implemented traverseInOrder() implementing the rest, traversePostOrder() and traversePreOrder() becomes that much easier since it is the same thing but doing things in different order, see below:&lt;/p&gt;

&lt;p&gt;function traversePreOrder( node, list ){&lt;br&gt;
//now we want to push at the very beginning because we start with the parent and&lt;br&gt;
then the children and that’s the order of preorder&lt;br&gt;
list.push(node.value);&lt;br&gt;
//checks for a left node&lt;br&gt;
//in the conditional, that recursive function will result in the node being passed in being&lt;br&gt;
pushed into the list array immediately, same for the other conditional for the right&lt;br&gt;
side&lt;br&gt;
if(node.left){&lt;br&gt;
traversePreOrder( node.left, list );&lt;br&gt;
}&lt;br&gt;
if(node.right){&lt;br&gt;
traversePreOrder( node.right, list );&lt;br&gt;
}&lt;br&gt;
return list;&lt;br&gt;
}&lt;br&gt;
//for traversePostOrder we would put list.push(node.value) at the very end of the function&lt;br&gt;
//this is because the order suggested is that we post at the end (postOrder), you can naturally see we must only push the leaf nodes then their parents and then slowly read in values one level at a time going from bottom to top&lt;br&gt;
function traversePostOrder(node, list ){&lt;br&gt;
//traverses all the way to the leftmost leaf node, puts that value into the list array,&lt;br&gt;
loops back out to the previous recursion and then moves down checking of there is a&lt;br&gt;
right child on the parent node of the leftmost leaf node (so this would record 1, the&lt;br&gt;
leftmost leaf node, and then go back up to the parent node and check the second&lt;br&gt;
conditional and see that there is a right node of 6 and push that into the list&lt;br&gt;
if(node.left){&lt;br&gt;
traversePostOrder( node.left, list );&lt;br&gt;
}&lt;br&gt;
if(node.right){&lt;br&gt;
traversePostOrder( node.right, list );&lt;br&gt;
}&lt;br&gt;
list.push(node.value);&lt;br&gt;
return list;&lt;br&gt;
}&lt;br&gt;
If you’ve noticed, we are using a stack data structure with the recursion.&lt;/p&gt;

&lt;p&gt;Each of these functions are added to our call stack and will start to return as they reach the end, which is when there’s no more left or right children, which means they’re at the leaf nodes.&lt;/p&gt;

&lt;p&gt;And this is important to understand, because it shows the space complexity of DFS (depth first search). The amount of space that we need in terms of memory, unlike BFS (breadth first search) which uses queues, is made apparent by the height of the tree because the height of the tree will match the deepest recursive function. And that’s what will be added to the stack as memory.&lt;/p&gt;

&lt;p&gt;This means our memory consumption or space complexity will be O(height of the tree) when using DFS.&lt;/p&gt;

&lt;p&gt;Conclusion&lt;br&gt;
Understand when to use BFS vs DFS and how to then implement this for graph traversal.&lt;/p&gt;

</description>
      <category>datastructures</category>
      <category>dfs</category>
      <category>javascript</category>
    </item>
    <item>
      <title>Introduction to Websocket — ActionCable: Real-Time Messaging</title>
      <dc:creator>Min Tu</dc:creator>
      <pubDate>Wed, 15 May 2024 02:30:57 +0000</pubDate>
      <link>https://forem.com/dispensableart/introduction-to-websocket-actioncable-real-time-messaging-1b08</link>
      <guid>https://forem.com/dispensableart/introduction-to-websocket-actioncable-real-time-messaging-1b08</guid>
      <description>&lt;h2&gt;
  
  
  What is a Websocket?
&lt;/h2&gt;

&lt;p&gt;A brief history before we delve into WebSockets, but before they existed, if we wanted something like “real-time” data, we would have to continuous fetches to the server at regular intervals.&lt;/p&gt;

&lt;p&gt;This would have been called polling. But because this means that the frontend would have to make continuous fetches, sometimes including fetches with no data whatsoever, this would clutter the call stack with unnecessary requests to the database.&lt;/p&gt;

&lt;p&gt;A websocket solves this by keeping the connection open on the client and server side until one or both sides disconnects.&lt;/p&gt;

&lt;h2&gt;
  
  
  Implementing Real-Time with ActionCable Overview
&lt;/h2&gt;

&lt;p&gt;We will have to create a Channel to make a chat room app.&lt;/p&gt;

&lt;p&gt;The process is:&lt;/p&gt;

&lt;p&gt;The client initiates a connection with a server via a WebSocket request. This will allow two-way communication.&lt;br&gt;
The server handles this by a specific feature called a channel. For our example, we can create a ‘chatroom_channel’&lt;br&gt;
After this connection is established (full-duplex communication), we can use this channel to broadcast messages to all users who are ‘subscribed’ to the channel (this, in our context, means that they have a chat window open).&lt;br&gt;
Steps:&lt;/p&gt;

&lt;p&gt;Create a chatroom channel on the server side&lt;br&gt;
Browser-side, we’ll use JavaScript (or React.js for a frontend)&lt;br&gt;
Then we:&lt;/p&gt;

&lt;p&gt;Broadcast the message to the frontend side where it is received.&lt;/p&gt;

&lt;p&gt;Then we display this data to the chat window or wherever we want it displayed.&lt;/p&gt;

&lt;p&gt;Here are some more abstract steps:&lt;/p&gt;

&lt;ol&gt;
&lt;li&gt;Generate chatroom channel&lt;/li&gt;
&lt;li&gt;Update messages_controller and create broadcast data to chatroom channel&lt;/li&gt;
&lt;li&gt;Write some JS to handle the data and receive data and append to chat window&lt;/li&gt;
&lt;li&gt;Update styling (such as scrolling)
We would generate our channel inside the app/channels folder with the name chatroom_channel.rb or like so _channel.rb&lt;/li&gt;
&lt;/ol&gt;
&lt;h2&gt;
  
  
  Generate a Chatroom Channel
&lt;/h2&gt;

&lt;p&gt;We need to run this command: $ rails generate channel &lt;/p&gt;

&lt;p&gt;So for us this would be: $ rails generate channel chatroom&lt;/p&gt;

&lt;p&gt;Which creates app/channels/chatroom_channel.rb which looks like this:&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;class ChatroomChannel &amp;lt; ApplicationCable::Channel
   def subscribed
       # establishing a connection to a channel
       # make sure you stream from the channel name for the channel
        stream_from “chatroom_channel”
   end
   def unsubscribed
      # Any cleanup needed when channel is unsubscribed
   end
end
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



&lt;p&gt;But the next thing we have to do is mount this to some route in routes.rb so our frontend can actually communicate with this channel in some way.&lt;/p&gt;

&lt;p&gt;So now, in our routes.rb, the way to mount this to a route:&lt;/p&gt;

&lt;p&gt;&lt;code&gt;mount ActionCable.server, at: ‘/cable’ → “/cable”&lt;/code&gt; being the route&lt;/p&gt;

&lt;p&gt;So now communication to the socket via that route, “/cable”, will be possible.&lt;/p&gt;

&lt;h2&gt;
  
  
  Modify and Broadcast Messages
&lt;/h2&gt;

&lt;p&gt;Now let’s figure out how to broadcast our messages to everybody connected to the channel:&lt;/p&gt;

&lt;p&gt;So now we need to go to our messages_controller.rb to alter the create route (this is the route that handles the POST of a new message to the messages table in the database) so that all new messages are broadcast.&lt;/p&gt;

&lt;p&gt;In your app/config/environments folder there are these three files: development.rb, production.rb, and test.rb…for the sake of production builds and deployment, we will need to use this:&lt;/p&gt;

&lt;p&gt;config.action_cable.allowed_request_origins = [‘https:// of your deployed app or something, this could be something in heroku-app or whatever’]&lt;/p&gt;

&lt;h2&gt;
  
  
  Displaying Messages by Appending new Messages to the screen when they are sent
&lt;/h2&gt;

&lt;p&gt;We need to handle this in the Messages Controller and inside the chatroom_channel.js&lt;/p&gt;

&lt;p&gt;Instead of partials which is what we would’ve used with Rails’s traditional MVC model, we’ll use frontend components in React. For this you need to append the message.body to the specific container you want.&lt;br&gt;
&lt;/p&gt;

&lt;div class="highlight js-code-highlight"&gt;
&lt;pre class="highlight plaintext"&gt;&lt;code&gt;class MessagesController &amp;lt; ApplicationController
before_action :require_user
   def create
      message = current_user.messages.build(message_params)
      if message.save
      # broadcasts to the specified channel that we made in the previous section
      # this takes and sends a hash (object), whatever is sent here is received inside our chatroom_channel.js in the received(data) {} section of that file
     # inside that chatroom_channel.js, we would reference this as data.mod_message
      ActionCable.server.broadcast “chatroom_channel”,
                                   mod_message: message.body
   end
end
private
   def message_params
      params.require(:message).permit(:body)
   end
end
&lt;/code&gt;&lt;/pre&gt;

&lt;/div&gt;



</description>
    </item>
    <item>
      <title>The useContext Hook: A Useful Way to Manage State</title>
      <dc:creator>Min Tu</dc:creator>
      <pubDate>Wed, 15 May 2024 02:24:25 +0000</pubDate>
      <link>https://forem.com/dispensableart/the-usecontext-hook-a-useful-way-to-manage-state-23dh</link>
      <guid>https://forem.com/dispensableart/the-usecontext-hook-a-useful-way-to-manage-state-23dh</guid>
      <description>&lt;p&gt;If you’re familiar with React, then you know data only flows one way from parent components to child components. If you want to make a state available to child Components then you have to continuously pass it down as props to the child components and even grandchild Components. You can imagine that this process would become tedious if your component tree has many, many children.&lt;/p&gt;

&lt;p&gt;You then risk your code becoming illegible or you might risk your code breaking in some way if you happen to make a typo or rename your props in some way when passing it down. Then this would now necessitate very, very thorough backtracking and waste valuable time that you could spend adding new features or refining your app, and nobody wants to waste time like that.&lt;/p&gt;

&lt;p&gt;This is where useContext comes in!&lt;/p&gt;

&lt;p&gt;In essence, the useContext hook makes a state globally available. You can inherit that state within any component. No longer do you have to occupy yourself with the task of passing down a state continuously. Now you can initialize a state or set a state within any component and have that state readily available in any component you choose.&lt;/p&gt;

&lt;p&gt;So how do we do that?&lt;/p&gt;

&lt;p&gt;Let’s say we want to initialize a simple state like isAuth with its setter setAuth and make that available in any component we choose. Then, to start, we need to make a .jsx file and import these two things:&lt;/p&gt;

&lt;p&gt;&lt;code&gt;import { createContext, useState } from "react";&lt;/code&gt;&lt;br&gt;
We need createContext to, well, create a Context and deem something as a Context and the naming convention for this is camel case, but specifically a type of camel case where the first word is also capitalized, so ours specifically would be called something like AuthContext. Since we want to export a boolean value and a state setter, which is a function, we want to put the “default values” into createContext. Note that these “default values” will never really be used and instead just serve as a pseudo-placeholder to define the data type of what’s being exported.&lt;/p&gt;

&lt;p&gt;So since we’re exporting a variable and function, we want to make sure that these two things are not defined, or are empty in the initial createContext function:&lt;/p&gt;

&lt;p&gt;&lt;code&gt;export const AuthContext = createContext({&lt;br&gt;
       isAuth:null,&lt;br&gt;
       setAuth:()=&amp;gt;{}&lt;br&gt;
});&lt;/code&gt;&lt;br&gt;
As you can see, isAuth is set to null and setAuth is set to an empty function, however, we have defined our exports as isAuth and setAuth. We will define what these two are in our Provider which is the part of useContext that allows us to pass down this state to child components. I will elaborate on this below, but the Provider exists so that we can wrap the components that we want to make this context available in, and we usually warp the  component with the Provider.&lt;/p&gt;

&lt;p&gt;The naming convention is also the same type of camel case as the context. Inside the Provider, we then need to actually initialize the state and state setter with useState that we want to export, keeping the same names as we defined in createContext.&lt;/p&gt;

&lt;p&gt;Then we create an Object called value that contains both the initialized state and state setter which the actual thing that we will export via the Provider. We then, in the return statement for the Provider, pass down the value Object as a prop. We also, in the parameters of the Provider, destructure a children prop so that we can wrap it with the Provider in the return statement to signify that anything wrapped by the Provider will inherit the state and state setter (or any other function) that we are exporting.&lt;/p&gt;

&lt;p&gt;See the below for the implementation of our example:&lt;/p&gt;

&lt;p&gt;&lt;code&gt;export const AuthProvider = ({children})=&amp;gt;{&lt;br&gt;
   const [isAuth, setAuth] = useState(false);&lt;br&gt;
   const value = {isAuth, setAuth};&lt;br&gt;
return(&lt;br&gt;
     &amp;lt;AuthContext.Provider value={value}&amp;gt;{children}     &lt;br&gt;
                                        &amp;lt;/AuthContext.Provider&amp;gt;&lt;br&gt;
     );&lt;br&gt;
};&lt;/code&gt;&lt;br&gt;
As you can see, in the return statement, we must export the Provider with the following name: .Provider. In our example this would be “AuthContext.Provider”.&lt;/p&gt;

&lt;p&gt;In order to make this state available in every component, we must go to our index.js and wrap our  Component with the Provider, like so:&lt;/p&gt;

&lt;p&gt;&lt;code&gt;const root = ReactDOM.createRoot(document.getElementById('root'));&lt;br&gt;
root.render(&lt;br&gt;
   &amp;lt;AuthProvider&amp;gt;&lt;br&gt;
      &amp;lt;App /&amp;gt;&lt;br&gt;
   &amp;lt;/AuthProvider&amp;gt;&lt;br&gt;
);&lt;/code&gt;&lt;br&gt;
This basically represents that we want to make the AuthContext available in the App component, which contains every component of our project, via our Provider, AuthProvider. Now you can access the state and state setter within any component!&lt;/p&gt;

&lt;p&gt;To access it within our child components, we must finally use the useContext hook and also import Context, AuthContext, inside it.&lt;/p&gt;

&lt;p&gt;Let’s say we have a child component that we want to import AuthContext into. To do so, we must need these two import statements in our child component:&lt;/p&gt;

&lt;p&gt;&lt;code&gt;import { AuthContext } from "./components/context/auth.context";&lt;br&gt;
import { useContext } from "react";&lt;/code&gt;&lt;br&gt;
We import useContext to actually access the contents of AuthContext.&lt;/p&gt;

&lt;p&gt;Now, in order to access the specific contents of our AuthContext, we must use useContext to destructure its contents like so:&lt;/p&gt;

&lt;p&gt;&lt;code&gt;const { isAuth, setAuth } = useContext(AuthContext);&lt;/code&gt;&lt;br&gt;
Remember that since our export is the value Object that we can destructure it like how we did above.&lt;/p&gt;

&lt;p&gt;Now we can go nuts inside our child Component and use the state or set the state however we want!&lt;/p&gt;

</description>
      <category>react</category>
      <category>javascript</category>
      <category>webdev</category>
    </item>
    <item>
      <title>Returning a Promise — How an async function operates</title>
      <dc:creator>Min Tu</dc:creator>
      <pubDate>Wed, 15 May 2024 02:22:46 +0000</pubDate>
      <link>https://forem.com/dispensableart/returning-a-promise-how-an-async-function-operates-21nj</link>
      <guid>https://forem.com/dispensableart/returning-a-promise-how-an-async-function-operates-21nj</guid>
      <description>&lt;p&gt;So you’re browsing the web.&lt;/p&gt;

&lt;p&gt;You hit the back button, and it loads the last page. This is the core concept of a data structure called a stack. The last thing added to the stack is the first thing out (LIFO). You know how you hit the undo button inside Word to revert to a previous change? That, too, is operating on a LIFO principle.&lt;/p&gt;

&lt;p&gt;This is the same way our JavaScript engine handles invocations of functions in the call stack. Since there is only one stack and function execution is done one by one from top to bottom, this means that the call stack is synchronous. In other words, because the stack can’t keep executing functions until the previous function is finished running, this is why the call stack is considered synchronous.&lt;/p&gt;

&lt;p&gt;However there’s a way to make a function wait until the call stack is done. We have to add a function to the callback queue so that something called the event loop will begin executing functions in the callback queue once the call stack is empty.&lt;/p&gt;

&lt;p&gt;The way we remove a function from the call stack is done is by defining a function as asynchronous.&lt;/p&gt;

&lt;p&gt;Have you ever seen a webpage that loads all of its HTML, CSS, and regular JS functionality first and then a second later, it populates those elements with fetched data? That’s the work of an asynchronous function.&lt;/p&gt;

&lt;p&gt;The main benefit of this is if a function in the call stack is going to take a long time, we can make sure to send it to the callback queue instead, taking it out of the call stack so it doesn’t hold up the rest of the function executions since the call stack is strictly synchronous.&lt;/p&gt;

&lt;p&gt;We usually do this with fetch requests, which by nature, are asynchronous.&lt;/p&gt;

&lt;p&gt;So then what are Promises and how do they relate to asynchronous functions? Well, the quirk about asynchronous functions is that they don’t return the return value specified inside them. They, instead, return a Promise that it will eventually either resolve to a value if fulfilled or fail if caught in an error.&lt;/p&gt;

&lt;p&gt;For example if you write “return ‘Hi there!’;’ inside an async function, it will return a Promise Object that is essentially this:&lt;/p&gt;

&lt;p&gt;new Promise(function(resolve, reject){resolve('Hi there!');})&lt;br&gt;
Think of it like this. We don’t actually know the value of the Promise when the async function is called. All we know is that the async function is run and it may or may not return a value, but it will definitely get back to us with something. This eventuality is captured by the existence of the Promise Object which is important in allowing us to associate event listeners or handlers with an async’s function success or failure.&lt;/p&gt;

&lt;p&gt;A Promise Object is always in one of three states:&lt;/p&gt;

&lt;p&gt;pending — this is the initial state of a Promise before it is either fulfilled or rejected&lt;br&gt;
fulfilled — the function associated with the Promise is successfully completed&lt;br&gt;
rejected — the function associated with the Promise has failed&lt;br&gt;
In order to actually work with the actual value that is returned by the resolution of a Promise, conventionally, we’ll have to chain on another asynchronous function called .then() which would also, since it is asynchronous, return a Promise. If we want to work with the resolution of a Promise then we would have to write our function inside of a .then() function.&lt;/p&gt;

&lt;p&gt;This diagram shows the flow of a Promise Object. It shows that the Promise Object has two paths, fulfilment or rejection. A Promise is considered settled once it resolves to either being fulfilled or rejected. We can chain on a .then() to the Promise to capture the return of a fulfilment or a rejection. If it is fulfilled, then we execute whatever is in the code block inside the .then() function and if it is rejected, we send it to error handling by catching the error in the .catch() chain.&lt;br&gt;
from mdn web docs&lt;br&gt;
But, within asynchronous functions and only within asynchronous functions, there is a way to assign the resolution of a Promise to a variable.&lt;/p&gt;

&lt;p&gt;First, we can make any function asynchronous by using the async keyword before the definition of a function:&lt;/p&gt;

&lt;p&gt;async function exampleAsync(){&lt;br&gt;
   return 1+1;&lt;br&gt;
}&lt;br&gt;
Note that this looks like we’re returning 1+1, but in actuality, we’re returning a Promise Object instead that, only upon resolution of that Promise, will resolve to the value 1+1.&lt;/p&gt;

&lt;p&gt;But within this async function, we can actually create a Promise Object or capture the return of an asynchronous function and set the resolution of either of those two things equal to the resolution of them.&lt;/p&gt;

&lt;p&gt;Think of it like this:&lt;/p&gt;

&lt;p&gt;async function exampleAsync(){&lt;br&gt;
   let fetchRequest = fetch('exampleApiUrl');&lt;br&gt;
   let fetchResult = await fetchRequest;&lt;br&gt;
   return fetchResult;&lt;br&gt;
}&lt;br&gt;
We know that the fetch() function is asynchronous and therefore returns a Promise.&lt;/p&gt;

&lt;p&gt;So if we said let fetchResult = fetchRequest without using the await keyword, shown above, we would simply be setting fetchResult equal to same Promise Object that fetchRequest is set to.&lt;/p&gt;

&lt;p&gt;But with the await keyword, we set fetchResult equal to the value of the resolution of the Promise which, if it’s a fetch request, is most likely a JSON. The await keyword means we wait for the Promise to resolve first before setting the variable’s value. This way we won’t be setting the variable equal to the Promise Object itself, but the value of the Promise’s resolution, which is something usable.&lt;/p&gt;

&lt;p&gt;Let’s use one last example with more concrete visual examples:&lt;/p&gt;

&lt;p&gt;async function exampleAsync(){&lt;br&gt;
   let examplePromise = new Promise(function(resolve,reject){&lt;br&gt;
      resolve(1+1);&lt;br&gt;
   });&lt;br&gt;
   let exampleResolve = await examplePromise;&lt;br&gt;
}&lt;br&gt;
We defined in our Promise Object that the resolution would be 1+1 if the Promise is fulfilled. Then we set the variable examplePromise equal to that Promise Object.&lt;/p&gt;

&lt;p&gt;If we didn’t use the await keyword when assigning exampleResolve, then it would simply point to the same Promise Object as examplePromise, but because we used the await keyword, it instead waits for a resolution and then sets the value of that resolution as the value of exampleResolve instead of the Promise Object itself.&lt;/p&gt;

&lt;p&gt;This is useful if we want to wait for an function to finish running first before assigning a value, essentially making something synchronous within an asynchronous function.&lt;/p&gt;

&lt;p&gt;It’s also useful to make our custom function asynchronous if we think it will take a long time to run, so we can actually define which functions we’ve written that we want taken out of the call stack.&lt;/p&gt;

&lt;p&gt;Make sure to use these concepts to your advantage in your code and to make your code that much more efficient!&lt;/p&gt;

&lt;p&gt;Cheers and good luck in your coding adventure!&lt;/p&gt;

</description>
      <category>javascript</category>
      <category>asynchronous</category>
      <category>webdev</category>
    </item>
  </channel>
</rss>
