DEV Community: Jenny Shaw

Now You Have a Job! But How Does Learning Fit in at Work?

Jenny Shaw — Thu, 07 May 2020 17:54:18 +0000

I'm now a professional junior developer, a little over 3 months in at very my first company, a tiny startup, and one of my team's biggest struggles has been figuring out how to integrate routine learning and education into a junior developer's work cycle.

I want to get the most out of my first dev job, especially as a junior dev of whom learning is expected! I want to help my team help me improve this aspect of my experience, so share your experiences with me here --

👉🏼 What have your companies done to make sure that you learn and grow as developers while also balancing work?

The Binary Numeral System (in Under 7500 Bytes)

Jenny Shaw — Mon, 06 Jan 2020 22:46:10 +0000

In this second article of my Unicode blog series, I'm going to introduce the binary system.

A computer accepts input, stores, processes, and outputs all data in binary -- that includes everything you consume on your computers, from the text and color on this page, to images, gifs, video, and sound.

So if we want to understand how Unicode is structured and how it's possible for us to have access and use over 150 scripts and over 3000 emojis, we need to understand a little about how binary works.

What are Binary Numbers?

Binary data is composed of 1s and 0s.

A binary digit, or a bit, is the smallest unit or building block of information that can be stored in a computer, and it can have one of two values, either 0 or 1. Varying sequences of bits strung together can each represent unique data. So, with more bits, we can compose more complex pieces of information.

Sizing Up

Decimal Values	Decimal Measure Names	Decimal Symbols
10⁰	Byte	b
10³	Kilobyte	KB
10⁶	Megabyte	MB
10⁹	Gigabyte	GB
10¹²	Terabyte	TB

Binary Values	Binary Measure Names	Binary Symbols
2⁰	Byte	b
2¹⁰	Kibibyte	KiB
2²⁰	Mebibyte	MiB
2³⁰	Gibibyte	GiB
2⁴⁰	Tebibyte	TiB

A byte consists of 8 bits. We'll discuss in more depth this later on as we discuss ASCII and Unicode, but a byte is typically enough to store 1 typed character. That means your longest tweet will usually max out at 280 bytes, or that 500-word cover letter I recently slaved over for a certain company was likely just under 3000 bytes, nearly 3 kilobytes -- but I won't dwell on that.

An image is composed of pixels each represented by a binary number. A high-resolution image can contain millions of pixels, which means that an image of that quality could be anywhere between 1 to 5 megabytes.

A video, basically a collection of sequential frames or images, run between 24 to 30 frames per second, and that's a lot more data than just one image! A YouTube video in HD could require as much as 12 megabytes per minute. But if we were to stretch to movie-length, then that could require as much as 4 gigabytes.

The amount of data required to fit a terabyte would be extraordinary. Check out the numbers from this blog and Dropbox and you'll quickly get the idea.

How Does the Binary System Work

I think it's easiest to explain the binary system by refreshing our memories with a system we're all already very familiar with.

Quick Review: The Decimal System

When we learned how to count bigger numbers in school, we were taught to memorize base 10 place values from right to left -- 1s, 10s, 100s, 1000s, and so on. And we learned that each place fit one digit, and each digit value or state could range from 0 to 9.

Base Ten	10³	10²	10¹	10⁰
Place Values	1000	100	100	1

So if we were to break down our present year, 2020, it would have a value of 2 thousands, 0 hundreds, 2 tens, and 0 ones.

Digit / State	2	0	2	0
Place Values	10³	10²	10¹	10⁰

So when we multiply the digits with their respective place values and sum them together, we get the value 2020.

Let's the math:

(2 * 1000) + (0 * 100) + (2 * 10) + (0 * 1)

= 2000 + 0 + 20 + 0

= 2020

Now Introducing: The Binary System

The binary system, on the other hand, has place values of base 2s.

Base Two	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰
Place Values	128	64	32	16	8	4	2	1

And the system has only 2 states available, 0 and 1.

Counting Up in Binary

So let's start counting. The first two numbers are easy --

0, 1...

Great! We made it this far -- But how do we count to the next sequence of numbers if we're limited to using only 0s and 1s?

Just like with the decimal system, we assign a state to each place value.

So, to count to two, we'd place a 1 over the 2s place.

Binary Number	0	0	1	0
Place Values	8	4	2	1

Let's find the decimal value here:

(1 x 2) + ( 0 x 1)

= 2 + 0

= 2

And to count to three, we'd place a 1 over the 2s and the 1s place.

Binary Number	0	0	1	1
Place Values	8	4	2	1

(1 x 2) + ( 1 x 1)

= 2 + 1

= 3

Good job! We can count to three!

Counting with the Bits You're Given

Currently, our tables contain 4 bits. If we were to max out all 4 bits, our largest value would be 15, (and the largest number of values 4 bits can store is 16 when we include 0).

Binary Number	1	1	1	1
Place Values	8	4	2	1

(1 x 8) + (1 x 4) + (1 x 2) + ( 1 x 1)

= 8 + 4 + 2 + 1

= 15

Handy Tip: If you have ten fingers to count with, you can count up to 1023 in binary!

Converting Decimal Numbers to Binary

Now, let's try converting our year into binary. Because 2020 is such a large value and well over 15, it's going to require a lot more bits.

	2¹¹	2¹⁰	2⁹	2⁸	2⁷	2⁶	2⁵	2⁴	2³	2²	2¹	2⁰
Place Values	2048	1024	512	256	128	64	32	16	8	4	2	1

To do this, we'll find the place that is equal our target value or the largest valued place that is less than our target value, and assign it a state of 1.

We subtract that place value, 1024, from our target, 2020. And that leaves us with the remainder, 996.

Then we repeat the process with the following place values. If our remainder is ever less than the place value, we assign it a state of 0 and move on to the next place. We continue this algorithm until we're left with a remainder of 0.

Here's our result!

	0	1	1	1	1	1	1	0	0	1	0	0
Place Values	2048	1024	512	256	128	64	32	16	8	4	2	1

Now we know -- 2020 is equal to 011111100100 in binary!

Note: Don't be fooled by place values. It's easy to see as above the 12th place of the binary system (2¹¹) having a value of 2048 and underestimate the potential of 12 bits. Don't forget that with 12 bits, by using every available place we can actually count up to 2¹² - 1. That's 4095 in decimal and nearly double in value! So remember that when we're provided with more bits, we get substantially more room for data.

Applying Binary to Character Encoding

If you read my previous blog on character encoding, you'll see that the binary system is important here because it is the language that computers communicate in and therefore essential for character encoding. And with more bits available, the more space there is to accommodate for more as well as more complex data, such as additional language scripts.

So, coming up in later posts, I'll discuss ASCII's 7-bit and Unicode's 16-bit encoding systems, how those systems and charts work, and what potential each of those systems can offer technologically as well as socially.

Decoding Character Encoding

Jenny Shaw — Mon, 30 Dec 2019 17:53:26 +0000

There was a time when...

...If my grandmother had typed out a message, "哈囉" (meaning "hello" in Chinese) and sent it out from her computer in Taiwan to mine in the US, I wouldn't have been able to read it.

You might think, But, of course! She was writing in Chinese, and your Chinese skills would've been too terrible back then to be able to read it!

(...which I suppose could have been true...)

...except that the message would've been unrecognizable and unreadable by anyone, including herself, once it had reached me! When I should've seen this message that she sent me, "哈囉," I might've instead seen something like "" or some other text that clearly wouldn't have read like Chinese. The same might've happened if a message was sent the other way around.

And that wouldn't have been my fault! Or my grandmother's!

For that, we could blame character encoding.

Before the standardization of character encoding in electronic communication, computers made by different manufacturers utilized different encoding schemas, which meant that even users communicating in the same language would've been presented with messy strings of nonsense (also known as mojibake) when receiving a message from someone else. By using different encoding schemas, their computers weren't "speaking the same language," and so they read the same data differently.

We take it for granted now, but with present standards for character encoding like Unicode and ASCII, problems like the one I just described are easily prevented from happening. They help us type, send, and receive data the way it was intended to be written and read, and they are what makes our computing and internet experiences productive and enjoyable.

What is character encoding?

Character encoding is using an encoding system to represent text characters like letters, numbers, punctuation, or spaces. One of the most famous and recognizable examples of character encoding is Morse Code, which is a system of letters and numbers that are each encoded into a sequence of dots and dashes. We could send an encoded message using those dots and dashes, and the recipient of that message could then translate it back into their own language.

In the context of computers, ASCII and Unicode are two encoding schemas that utilize the binary number system. Computers can't read human languages, but they read binary numbers super well, so both schemas assign characters to binary numbers so that computers can read the binary sequence and convert it into a language we can understand.

How does it work?

The ASCII conversion table with code points assigned to each character

Let's assume that our computers both use ASCII's encoding schema. ASCII has the capability to support 127 different characters, and each character is assigned a code point. The code point can be a unique decimal number between 1 and 127** as well as a unique binary number whose value is between those numbers. The decimal code point for the character “A” is 65, which is represented as 1000001 in binary.***

So, if I were to type out the letter “A” on my keyboard, the keyboard would send the binary sequence, 1000001, to the computer, which would then look up the ASCII table to convert the binary code point to the character "A" for display on my screen.

When I send it to your computer, it wouldn't be sent as the character "A", but as its binary code point. When your computer receives the message, it would also use the ASCII table to decode and convert the binary code and display the expected “A” onto your screen.

If, however, your computer had utilized a different encoding schema where code point 65 was assigned differently (let's just assume it was assigned to "Z"), you would have read "Z" because was converted according to that specific schema rather than the ASCII schema.

Why is character encoding important?

If the reasons aren't obvious by now, character encoding, especially standardized character encoding, is important because it helps all parties understand each other. It helps us as users to communicate with our computers, and it helps our computers transmit and receive accurate data so that we can also communicate with each other!

Notes About This Series

This is the first blog of my new series on standardized character encoding and Unicode. Over the following month and a half, I'll be explaining how the binary system works, diving into ASCII and Unicode, and discussing why Unicode is especially important to our global community.

Character encoding itself is pretty straightforward, but I believe that as we dive deeper into it together, you'll be very surprised by how multifaced and fascinating the topic can be! This series deeply involves many of my personal passions, not just technology, but also language, culture, and social issues.

I'm so excited to share these upcoming blogs with you, and I really hope you'll follow along!

Footnotes:

** Technically, there are 128 code points in the ASCII range, but 0 is assigned as a null character, so that leaves 127 usable code spaces.
*** It's worth noting that decimal code points are meant for human readability, but binary code points are for computers.

Tired of LinkedIn? 5 Ways to Search for Your Next Job

Jenny Shaw — Sat, 28 Dec 2019 01:54:05 +0000

When I first started my job search, the only way I knew to look for open positions was to browse through the most popular and common internet job boards such as Glassdoor, Indeed, or LinkedIn. And although they're all fantastic websites, I've learned over time that I much prefer to actively engage in the search by using other resources, ones that appeal to my personal interests, specific skills, and diverse background, and especially ones that involve more human interaction.

1. Meetups and Conferences

Meetups and conferences are a great way to find job opportunities through personal connection building. At any event, you could meet someone who knows about an open position in their own or a friend's company, or at some larger events, you could browse job fairs or sponsored tables run by companies looking to hire. No matter what the event is though, it's always a chance to meet recruiters and other professionals and to make first-impressions far more memorable than your paper or digital resume.

Here are some meetups and conferences that I've had great experiences with:

Some people stress out over about these in-person interactions and worry that they'll appear more thirsty and less genuine. But try to remember a lot of these meetups are made to facilitate connections and help them happen organically, and also remember that other people are attending these same events to have a good time and to bond over similar interests and causes. So just show up, be polite, and be yourself. And if you find that you like and care about the event enough to attend regularly, you'll soon enough find that you're part of a community that cares just as much about you and wants to contribute to your success.

2. Diversity Job Boards

As a queer woman of color, it's extremely important to me that I find companies and teams that see value in diverse people and want to support them, so I try to access and utilize communities that I identify with as much as possible.

In addition to the job boards of some meetups I attend, here are a few other favorites:

Also, there is definitely something to be said about companies that go out of their way to post on diversity job boards. To me, it's a strong indication that they want to create a diverse team, that they have an interest in the individuals in their company and what they can contribute, and that they value change and progress. So, whenever I see a job listing on any of these boards, I tend to be more interested and hyped about the company that posted it.

3. Networks from a Past Life: Alumni, Club, Societies

I'm very lucky and privileged to be a part of many social networks, and I try to take full advantage of that by staying connected to as many organizations, clubs, and schools I've ever been involved with -- That includes my middle school, high school, college, semester program, bootcamp, and sub-chapters of each, like an LGBTQ or Seattle chapter if those exist as well.

If you were part of a sorority or fraternity, a club, a specific school department, or whatever else you can think of, try to reconnect with those groups through all their social media sites. Follow them everywhere -- on Facebook, LinkedIn, Instagram, even Twitter -- introduce yourself, broadcast that you're on the market, and check regularly to see if anyone has any leads on job opportunities. People who are active in these groups are often eager and excited to help out members of their own community, so let them help you!

4. Online Community Newsletters

A small thing I do to expose myself to jobs that either I'll be more interested in or I'm better suited for is subscribe to various newsletters. I subscribe to the newsletters of diversity organizations like the ones I listed above and to tech-specific news digests like Javascript Weekly or React Status, which not only keep you up to date on new changes but also include job listings that are often skill-specific.

5. Slack and Social Media

To make sure that I fully take advantage of any tech community, meetup, or event, I always make sure that I join their Slack group. If that option doesn't exist, then I'll look into LinkedIn, Facebook, and Twitter groups.

Slack is great because most tech groups have a jobs channel or channel specific to your region where people share with the community about job openings and are enthusiastic to talk about their company and the role. If you reach out to them, some may offer to connect you with a manager or recruiter, or they may even offer to refer you.

Combine Slack with LinkedIn, and you can more effectively research the company and play the networking game that helps get you one degree closer to communicating with someone who works at your dream company.

Final Thoughts

Using websites like LinkedIn and Glassdoor makes plenty of sense -- Almost every hiring company and job-seeker uses them, so there are always plenty of new job openings and updates to browse there, and the possibilities are endless. But for me, there can be such a thing as too many possibilities -- I could scroll through generic LinkedIn listings forever and ever, and that can feel overwhelming very quickly.

Also, as a career-changer, having a curated feed isn't always helpful because those websites may return jobs I qualify for based on my skills and experiences I had (in education, management, and fitness), and not the jobs I want in software engineer.

Most importantly though, what these websites don't consider are my interests and who I am as a person. I'm a software engineer, yes, but I'm also a career changer, a bootcamp graduate, and a self-learner. I identify as queer, a woman, a person of color, Asian, and Taiwanese-American. I care about learning, education, and social justice. I want to find a company that's going to value and embrace me for all of these qualities and interests, but I won't easily find that match through a giant job board, nor will I easily stand out among an ocean of candidates. That's why I think it's important to use these other specific resources in addition to the usual job search engines.

The only big disadvantage to using these resources is that it takes more time and effort to comb through all the options, and some opportunities only come by chance, but the extra effort is worth it -- I'm much more motivated and engaged in the job search, and I'm actually excited to find jobs and companies that I can actually see myself working in!

I'm always looking for more resources that I can use and that I can share with others. If there are any awesome ones you love to use, share them in the comments below!

Binary Trees (Part 5) - Stay Abreast of Breadth-First Search

Jenny Shaw — Mon, 16 Dec 2019 17:39:22 +0000

This week's blog post is a continuation of last week's article about Depth-First Searches and Traversals in binary trees where I briefly compared Depth-First (DFS) and Breadth-First (BFS) Searches and then went into more depth explaining three common DFS methods: in-order, pre-order, and post-order. For today's blog post, I'd like to discuss a couple of situations where we'd use DFS or BFS, and also share some code to explain how BFS works.

A Quick Review of DFS and BFS

As discussed in my previous post, DFS allows us to recursively traverse through a binary tree, diving deeply, edge-by-edge, and exhaustively exploring one branch of a tree before backtracking to the next unvisited branch, whereas BFS or Level-First Traversals allow us to visit nodes of the tree level-by-level.

Here's an (imperfect, but relatable) metaphor to help us visualize how DFS and BFS might process nodes.

Imagine the binary tree as a buffet spread -- a long counter lined with various trays of food. DFS and BFS are eating tonight, and each has a different strategy for dining and traversing this buffet.

BFS, like most of us, would take a serving of each dish onto its plate as it makes a single pass along the buffet counter. After it completes a pass, it would return to the start of the buffet counter and go another round. Each time, the food in all the trays would make it onto BFS's plate and eventually into its mouth.

DFS, on the other hand, would start at the first tray of the buffet counter lineup and keep scooping food until it's reached the bottom of the container. And only when it's completely emptied that tray, it would move onto the next tray in line and proceed to empty that one as well.

Breadth-First Search

In BFS, we traverse a tree from top to bottom, left to right, so when we're processing the node values, we're doing so across levels. After we've exhausted all the nodes in a level, we proceed down to the next level.

Steps to Breadth-First Search:

Before beginning the search, create the following:

a queue to keep track of all the nodes and their children that we'll need to process and
a result array to print the nodes in order.

To begin the traversal, first push the root node into the queue. Then,

Assign the first node in the queue to be the current node,
Process/Print the current node,
If the current node has a left child, push the left child node into the queue,
If the current node has a right child, push the right child node into the queue, and
Shift or remove the first node from the queue.

Repeat steps 1 - 5 until the queue is empty again.

Code: Printing Nodes in BFS Order

bfs(root) {
  let result = [];
  let queue = [];

  queue.push(root);

  while(queue.length) {
    let curr = queue.shift();
    result.push(curr.value)
    if (curr.left) {
      queue.push(curr.left)
    }
    if (curr.right) {
      queue.push(curr.right)
    }
  }

  return result;
}

Code Explanation:

You may recall that in DFS, we'd traverse a tree using recursion. The call stack that results from recursion would help us keep track of which node needed to be processed or bookmarked for later.

However, in BFS, we'd use a queue* to keep track of the nodes that need to be processed. The first in the queue is always the current node, and it's usually followed by a sibling node or a descendant node of the next level below. When we handle the current node, we process its value before we add their left and right children to the queue so that they can be processed later.

What are other differences between DFS and BFS?

As far as run-time goes, DFS and BFS are the same at O(V+E) (V for vertices and E for edges) or simply O(N) because both searches will visit every node in the tree once.

And with regards to extra space, DFS requires O(H) space, where H stands for the maximum height of the tree. It requires O(H) space because of recursion and the function call stack that stores all the node ancestors as we traverse further down the tree. BFS also requires extra space, O(W), where W stands for the maximum width of the tree. This is because the queue at a maximum must keep track of all of the descendants at the widest level of the tree.

What can we do with DFS and BFS?

Now that we know how DFS and BFS work, we need to know what advantages one has over the other and situations when these searches could be applied!

A target or a solution's distance from the root can be a deciding factor in which search to apply. For example, if we suspect that a target node is located deep inside of a tree, possibly closer to a leaf node, we might opt to use DFS because it searches nodes from leaves to root. However, if we're fairly certain that a node is located closer to the root instead, it would be wiser to use BFS since it searches from root to leaves.

In addition, if you're searching for the shortest path from root to node, BFS is an obvious and efficient choice. DFS, however, is less ideal because even though it will always find the target node, it may not take the shortest route, especially because of how it dives deeply in and out of branches.

Finally, DFS is more suitably used for games where decision making is involved in finding a solution. Think of finding the exit in a maze or encountering success in a quest or choose your own adventure game. BFS wouldn't be as useful in these situations though because it doesn't exhaustively explore paths the way that DFS does. However, while we're still on the topic of games, BFS is more concerned with finding the shortest path, so it might be better suited for a puzzle like a Rubik's cube where the goal is to solve the puzzle, not after exhausting all possibilities, but in as few turns as possible.

Check out these pages by GeeksforGeeks if you're interested in learning more about where to apply Depth-First and Breadth-First Traversals!

Conclusion

That's all for Breadth-First Search, and for all things binary trees!

This Binary Tree Blog Series all started with a couple of binary tree problems that I wasn't able to solve and then an obsessive desire to understand it better. This series is by no means a full and comprehensive guide to binary trees, but I hope that it's informative enough to help ease other newbie programmers like myself into learning more about the topic!

Thanks for reading and learning along with me!

For more information on binary trees, check out these other blogs from my 5-part binary tree series!

Footnotes:

What's the difference between stack and queue data structures? A queue is like a waiting line at a cafeteria, where the first person to show up is also the first to be served and to leave. A stack, on the other hand, is much like a stack of dishes or trays at the cafeteria, where the first ones placed into the stack are later always the last ones to be taken out and used.

Binary Trees (Part 4) - Discussing (in) Depth-First Traversals

Jenny Shaw — Mon, 09 Dec 2019 17:10:32 +0000

Prerequisites:
It'd obviously be beneficial to have some knowledge of binary trees and binary-search trees since this article is about binary tree traversals. Also, a concept that is frequently mentioned here and used in the context of binary trees is recursion. If you're not familiar with any of these, I'd highly recommend you catch up on them first before reading further.

Traversing Through Binary Trees

This week, we'll be exploring Binary Tree Traversals!

Not this kind of tree traversal, although sometimes the struggle feels the same.

First, I'll briefly explain the two types of traversals and searches, Depth-First Search (DFS) and Breadth-First Search (BFS). Then, I'll focus on the three DFS methods, Pre-, Post-, and In-Order. For each one, I'll share a tip to help you remember how each traversal works, explain how the traversal is used, and demonstrate what it would look like visually and in code.

Sounds like an adventure! Let's go!

First, a Quick Story about Tree Traversals and Video Games

Betrayal at Krondor - the greatest RPG of all time

I remember obsessively playing my all-time favorite RPG, Betrayal at Krondor, and spending many endless hours getting helplessly lost trying to explore various towns, caves, tunnels, and other maze-like areas. There were times when I got so frustrated, I would reset the level so that I could strategize and test new ways to get through them without wasting so much effort.

Here was the strategy I ultimately came up with:

Whenever I encountered a split in the path, I would always take the left turn.
And when I ever encountered a dead-end, I would backtrack to the split-off where I would take the next unexplored path to the left.

This strategy worked extremely well for me in the end because decision-making at the crossroads was a super straightforward process that required very little thought, and I never experienced again the same level of head-spinning confusion and anguish that I had when I was choosing paths arbitrarily. Most of all, I was able to explore every single path and find every treasure chest, character, and baddie that existed within the maze. And I was always able to (eventually) find the exit.

The best part of recalling this experience is realizing that, as a child, I was unknowingly applying a common binary tree traversal strategy, in-order traversal!

Now you know that the traversals we'll learn about here aren't just for trees: they can be applied to real-life situations, and you've probably already been using them!

Let's Get into Binary Tree Traversals!

So, what does it mean to traverse a tree?

To traverse means to move or pass through, so when we're traversing and searching through a tree, we're moving through it by visiting each node along every branch until we encounter what we're looking for.

When any node in a binary tree could potentially branch out in two directions, it can quickly become overwhelming and confusing for us when we have to consider efficient yet thorough ways to traverse the tree and find the target value. It's a lot like finding the exit in a maze without a map.

Fortunately, there are several commonly used methods that can help us systematically traverse through trees!

Depth-First Search vs. Breadth-First Search

There are two broad categories of tree traversals and searches, Depth-First Search (DFS) and Breadth-First Search (BFS). Both use unique approaches that allow us to visit every node in a tree.

Depth-First Search focuses on recursively processing nodes along a path between the root node and the leaf nodes. So imagine we're traversing straight down a path -- when a leaf node is finally reached, we backtrack from there and return back up our previously traversed path until we reach the first un-explored branch, and then we traverse that branch. This cycle of exhaustively exploring then backtracking repeats until all of the nodes of the tree have been visited.

Breadth-First Search is also known as a Level-First Search (Personally, I prefer the term Level-First because it emphasizes the concept of traversing by levels. That - and I like simple words.) With BFS, we search all the nodes level by level, from the top of the tree to the bottom. This means that at the first level, we'd visit the root node, then on the second level, we'd visit its two children, and at each deeper level, we'd visit all the descendants of that same generation, including children, their siblings, and their cousins.

Depth-First Traversals

Here, we'll focus on these three Depth-First Searches.

Pre-Order
In-Order
Post-Order

Each of these traversal methods is an algorithm or set of directions that dictates the order that we visit nodes and their subtrees.

Search	Order
pre-	ROOT	left	right
in-	left	ROOT	right
post-	left	right	ROOT

Although the traversal order changes with each method, there's one pattern that remains consistent: The left node is always visited before the right node.

Also pay attention to the prefixes of each search name because they'll help us better anticipate and understand what's going on.

Pre- means 'before', so in this order, the root will be visited first before either the left or right nodes.
Next, think of -in as in inside, and see how the root is located in the middle of the node order.
Finally, -post means 'after', so in this order, the root will be visited last, after the left and right nodes.

Now you can easily remember the respective orders of pre-order, in-order, and post-order!

In-Order - Left, Root, Right

With an in-order search, we traverse the tree from left to right, bottom to top, and its often used to print out a list of visited nodes.

When used on a Binary-Search Tree where values are sorted with smaller values to the left and larger values to the right, you'd get a list of increasing values.

Steps to In-Order Traversal:

Traverse the left subtree by recursively calling inOrder function
Process the root value by pushing it into nodes
Traverse the right subtree by recursively calling inOrder function

Code: Writing the inOrder Function

let nodes = [];

const inOrder = root => {
  if (root.left) inOrder(root.left)
  nodes.push(root.value);
  if (root.right) inOrder(root.right);
}

inOrder(root);
return nodes;

Before writing the inOrder function, we assign an empty array to a variable called nodes, which will later compile a list of node values processed in-order. As we traverse the tree, new node values will be added to it.

inOrder is the function that will determine the steps and order that nodes will be visited. By using it we'll recursively traverse the left subtree, process the node, then recursively traverse the right subtree.

Code Explanation

Let's say we call the inOrder function on the root node at the top of the tree. From the root node, we check for a left node, and if one exists, the function calls itself again using that node. Then from that node, the process is repeated. As we move down the tree leftwards, we're creating a stack of inOrder calls until we can't move leftwards anymore.

When we finally reach the leftmost node at the end of the branch, the most recent inOrder call runs the following line that pushes the root value to nodes, and then the last line that checks if there's a right node to traverse. (In this case, there isn't, but if there were, inOrder would be called again to process the right node and its descendants.)

When that most recent call is complete, it's removed from the call stack, and as a result, we backtrack to the previous node that inOrder was called with, process that node there, then follow down its right subtree.

Pre-Order - Root, Left, Right

Pre-order search, similarly to in-order search, lets us print a list of the visited nodes, but this time from top to bottom, left to right. Pre-order traversal is often used to copy a tree.

Steps to Pre-Order Traversal:

Process the root value by pushing it into nodes
Traverse the left subtree by recursively calling preOrder function
Traverse the right subtree by recursively calling preOrder function

Code: Writing a preOrder Function

let nodes = [];

const preOrder = root => {
  nodes.push(root.value);
  if (root.left) preOrder(root.left)
  if (root.right) preOrder(root.right);
}

preOrder(root);
return nodes;

Code Explanation

The process for pre-order search is very similar to in-order search, only that the order of nodes processed is rearranged to root, left, then right.

When we want to construct a binary-search tree or a new tree, we can use the pre-order as well as in-order lists to help us build it from the top down. The root node, the first of the printed list, would be established first before introducing the children nodes that connect to it.

Post-Order - Left, Right, Root

Post-order traversal can be used to delete a tree one node at a time, starting with the children, then their parent, all the way up to the root node.

Steps to Post-Order Traversal:

Traverse the left subtree by recursively calling postOrder function
Traverse the right subtree by recursively calling postOrder function
Process the root value by pushing it into nodes

Code: Writing the postOrder Function

let nodes = [];

const postOrder = root => {
  if (root.left) postOrder(root.left)
  if (root.right) postOrder(root.right);
  nodes.push(root.value);
}

postOrder(root);
return nodes;

Code Explanation

Post-order traversal is almost the reverse of pre-order. While pre-order processes root, left, right, essentially from top to bottom, post-order processes left, right, and root, from bottom to top.

If we were to apply it by deleting nodes from a tree, we'd process each external or leaf node, assign null to it, and effectively remove each one from the tree, then exposing internal nodes and making them the new leaf nodes ready to be removed later.

Wrap-Up & Conclusion

That's it for Depth-First Traversals! There are many other kinds of depth-first traversals

That was a lot of information to take in, but now that you know more about traversals, they probably seem a lot less scary and overwhelming than before!

Next week and coming up last in my five-part Binary Tree series is the Breadth-First Traversal! Whew! We got this!

Resources:

If you want to see a video demonstration of all three depth-first traversals, this is an excellent view:

Binary Tree Bootcamp: Full, Complete, & Perfect Trees. Preorder, Inorder, & Postorder Traversal. - Back to Back SWE

If you're interested in knowing more about constructing binary-search trees with in-order and pre-order sequences, check out these links:

Construct Tree from given Inorder and Preorder traversals - GeeksForGeeks
Build a Binary Search Tree from a PreOrder Sequence - Techie Delight

And for more about deleting trees using a post-order sequence, take a look at this:

Write a Program to Delete a Tree - GeeksForGeeks

For more information on binary trees, check out these other blogs from my 5-part binary tree series!

Give Yourself Some TLC with Some TDD (Test-Driven Development)

Jenny Shaw — Mon, 02 Dec 2019 21:48:56 +0000

Test-Driven Development, or more simply TDD, is a development technique of writing tests prior to writing code to fulfill those tests. It's a technique that's reputed to be underappreciated and underused, however, there are many excellent benefits to using it, especially when it's implemented correctly.

A lot of developers might skip over test-writing because they feel it's tedious and time-consuming. They may believe that manual testing and debugging tools are sufficient enough for gauging the functionality of their code, and that all the time spent writing tests could instead be put towards just building and completing their tasks sooner.

But before I share with you the benefits of TDD, allow me to first share a couple of personal experiences and scenarios where this sort of mindset I described can actually be debilitating to your workflow, your productivity, and your mental health.

Scenario One

There was a time when I thought I was a pretty good developer...

What I mean by that is that with skills and knowledge aside, I have many personal qualities that contribute to making me a good developer. For example, I'm organized and meticulous, and I try to prevent mistakes by planning ahead before starting any writing.

But...I'll fully admit that my "planning" sometimes only takes place in my head...

...so sometimes, I might get sidetracked as I'm working...

...then sometimes, I'd fall down a deep, deep rabbit hole, and eventually lose track of what I'm doing...

...and sometimes...

...just...sometimes...

...I might entirely forget what I was doing to begin with.

And just like time itself, the task I was working on passes with it, silently and without me ever noticing.

Scenario Two

Code is EASY! Until there's more of it...

I like to believe that for the most part I think critically and carefully. I enjoy problem-solving and building, so it's fun and satisfying for me to write a few lines of code, run it, and instantly watch it work. I also like the challenge of writing longer, more complex lines of code. By manipulating multiple moving parts, finding ways to bring and bind them together into a smoothly operating machine, it feels like I'm performing the perfect juggling act. However, if there's so much as a single-letter typo, I get a broken, non-functional app and wasted hours filled with frustration and humiliation.

Like any person when given enough time, I'll make the occasional mistake here or there while writing long snippets of code. I'll continue building up, manually testing, sometimes even blindly trusting my code. And everything seems fine until I find a bug. Not a big deal, though. Bugs are common. I'll just patch it up. Easy peasy.

But I debug it, I'll find something else that was previously working perfectly fine now broken. Then I'll work on that bug and effectively break something else. That chain will continue, and by then it'll be especially clear and visible to me that the problem did not simply stem from just one small bug, but from a series of bad foundational habits. At that point, it feels near-impossible to draw a clear line between the buggy feature and the single-line of code that caused it, and what follows may be many anxious hours of debugging and scanning through hundreds of lines of code.

And during those long tension-filled hours, I'll also spend deeply and regretfully reflecting on how I could've made better choices and better spent my time.

Allow me a moment of denial

But, but, BUT... I had reasons for doing things the way that I did.

I was on a deadline! I just didn't always have time to write out careful, detailed plans!
And it seemed easier and more productive to just tap into my manic energy and type frantically as I things came to my head! I swear, it really felt like I'm getting things done faster.
And mistakes happen! They're natural! And I thought I was sharp and SMART! With my massively-oversized confidence, I thought I'd make fewer mistakes. With my eagle eyes, I was sure I'd see errors as they presented. And with my powerful brain, I knew I'd eventually find some way to debug them!
Besides, I may not have known exactly everything that I wanted and needed to do right at that moment, but I understood the bigger picture, and I knew what I wanted to do next. I figured that everything in the middle would eventually fall into place.

Snap back to reality

I know now that all of those reasons were just excuses for poor habits and mediocre outcomes. After my last couple of experiences developing small projects using TDD, I've truly grown to appreciate tests and the time that I take to write them. And it's remarkable how much it's improved the way that I think about problems and progress through my code development.

Top 10 List: Benefits to TDD

Despite most people's attitudes towards Test-Driven Development, I have experienced these upsides to using the technique.

It's helped me think critically about my code.
It encourages me to plan ahead before blindly diving into a project.
It creates a tighter, faster feedback loop, allowing me to catch errors more efficiently and code more confidently.
It is 100% supportive of my experimental endeavors and efforts to improve and refactor my code.
Continuing on from the previous two points, it helps keep my code tidier, DRYer, and less prone to bugginess.
It doubles as documentation that clearly communicates to you and others who read your code what you're trying to accomplish.
It helps me set goals, and keep me focused and on task.
It's an objective communicator that helps bring transparency to where my code is functioning correctly and where it's not.
It brings clarity to my workflow and minimizes my stress.
Most of all, it improves my happiness.

TDD - Excellent for Mental Health and Productivity

I want to focus on the happiness aspect of TDD. Without sounding like some cheesy self-help author, I honestly feel that Test-Driven Development has helped my mental health.

Before TDD

As I used to code out projects, I often watched my confidence like a rollercoaster dramatically rising and dipping, and it exacerbated a lot of my problems with anxiety and my self-image.

Encountering surprise bugs or ones that were time-consuming to fix led me to believe that I wasn't a strong developer. That, in turn, made me frequently second guess my decisions and question my knowledge and abilities. And as I was consumed by imposter syndrome, I would become paranoid about making mistakes, and then I would have extreme anxiety about my poor time-management and my lack of focus.

I wasted a lot of time overthinking a problem to make sure I got a solution right the first time (and as would be expected, it rarely happens that way), or I wasted time debugging my way through a chain of broken features. And no matter how much I tried to compensate for all of those issues, no matter how hard I worked to keep my code functional and clean, nearly 100% of the time, I had to accept my work as it was, brittle and fragile, and there was no room to improve without risking the chance to completely break everything. I was utterly saturated with stress.

How TDD Helped Me

Test-Driven Development can prevent this downward spiral from happening. In a way, TDD is a lot like journaling. I document my goals, and then I focus on them. And as I accomplish those goals, I celebrate my success with a checkmark, and I move on to the next task.

But what makes TDD even better than that is that my tests instantly communicate with me, signaling back and forth between red and green, letting me know what's going wrong or right. And so, instead of coding blindly and helplessly, I'm actively being guided and encouraged by my own tests.

TDD helps give me many reasons to be happy. It helps me stay focused and productive and saves me time from debugging, which means I can use that time to do other fun and enjoyable things. It provides a clear sense of progress and acknowledges my wins and successes. Most of all, it helps me shed my anxiety and allows me to code with greater confidence.

Resources

If you haven't had a chance to try out Test-Driven Development, I really recommend that you do! Here are a few free resources where you can learn about a few of the testing frameworks and libraries available out there.

If you had to choose to look through only one of these, I highly, HIGHLY encourage you to check out Fun Fun Function. The host of the channel, MPJ, does a fantastic job acting out all of the thoughts, feelings, and perspectives around TDD as he teaches Jest basics.

Fun Fun Function - Video Playlist on Unit Testing
The Odin Project - Testing Basics with Jest
freeCodeCamp - Information Security and Quality Assurance Certification with Chai

Binary Trees (Part 3) - Deleting Nodes in Binary-Search Trees

Jenny Shaw — Mon, 25 Nov 2019 17:54:19 +0000

Node deletion was a basic method that I at first struggled with while learning how to manipulate Binary-Search Trees (or BSTs). Already knowing how to delete nodes in a Linked List, I thought I could apply the same concepts and processes to a BST, but in cases deleting a node wasn't as intuitive as I expected it to be.

In this blog, I'm going to compare deleting nodes in a Linked List and in a Binary-Search Tree and discuss how the processes are similar, and where they differ. I'll also code a class method and a function that removes nodes, and I'll explain the code as I write it.

Review: Deleting a Node from a Linked List

For those of you who are familiar with Linked Lists, the process for deleting a node from one is simple. You traverse through the list until you find the node that you want to delete. If that node happens to be at the end of the list, just delete it by pointing the previous node to null. And, poof, gone. It's as simple as that.

Deleting a node in the middle of a list, however, requires a little more effort. If the target node falls in the middle of the list, we can't simply delete it because if we do, we also end up trashing the remaining successive nodes that it points to. That would be a massively unfortunate mistake whether you did that with a Linked List or with a BST. Here's a dramatized example of what that could look like in a BST.

So, to avoid losing the rest of a Linked List, we point its previous node to its next node. By re-directing the previous node's pointer this way, we cut off any reference to the target node, essentially deleting it.

The Challenge: Deleting a Node from a BST

Knowing what I knew about Linked Lists, I assumed that it'd be just as simple to delete nodes in a BST. And in most cases, I was right.

Deleting a Node with 1 or Fewer Children

In the case that the target node was a leaf at the end of a branch, we'd just delete it.

And if the target node were to have only one child, we would just connect that node's parent to its child.

But, here's where my assumptions were wrong and insufficient. Unlike a Linked List, BSTs don't follow a linear sequence where one node is followed another, which is then followed by another. Nodes in a BST branch out and could have as many as two node children, a left and a right. So you might ask some questions like,

1) How would we choose which of the node's children to connect to its parent? And after choosing,
2) How would we reattach and restructure the other child subtree so that we maintain the hierarchical rules of BSTs?

Thankfully, we don't have to worry about either of these questions because there's a special, yet straightforward approach to handling this problem.

Deleting a Node with 2 Children

What we do is after we find the target node, we mark its place, and we continue traversing down the branch, first by moving to the first right child, and then continuing to move down the branch, moving as far leftwards as possible until we reach a leaf node.

The leaf we visit would have the smallest value of all the target node's right and larger-valued descendants, which makes it a perfect substitute for the target node we're about to delete. As the target's replacement, it keeps everything in order as it already is. Its left descendants still have smaller values than it, and its right descendants also still have values greater than it, and it maintains the bridge between upper and lower levels of the branch.

Write Code: deleteNode()

In my previous blog, we learned how to get started coding BSTs (creating Node and BST classes, insert and find methods). We'll continue from where we left off last time and write the deleteNode method step by step.

Setting Up: Create Remove Method and a Helper Function

  remove(value) {
    const removeNode = (node, value) => {
      // EVALUATING NODE
      // REMOVING VALUE
    }

    this.root = removeNode(this.root, value);
  }

Create a method called remove that takes a target value as an argument.

And inside of our method, we'll create a helper function called removeNode. It'll be responsible for actually removing the node value in the tree, and we'll be using it recursively. This function will take in two arguments, a node and a value (the same value as the target value or the value of the node we want to remove). We'll call the function inside the remove method, and it will take in our root node as its first argument.

Compare Target and Node Values

const removeNode = (node, value) => {
  // if no node exists, return null
  if (!node) {  
    return null;
  }

  // *** COMPARE TARGET AND NODE VALUES BELOW***

  if (value == node.value) { // if they match, 
  // REMOVE VALUE HERE

  } else if (value < node.value) { // if target value is lesser than node value,
    // search and remove target in left subtree
    node.left = removeNode(node.left, value); 
    // return updated node after removal
    return node; 

  } else { // if target value is greater than node value
    // search and remove target in right subtree
    node.right = removeNode(node.right, value); 
    // return updated node after removal
    return node; 
  }
}

Inside of remove node, we're going to check first if the node is even valid. If it isn't, then the tree doesn't exist, and we just return null.

Following that, compare this node's value against the target value. We want to check to see if it matches or not. If it does, we'll take further steps to start the removal. If it doesn't, we see if the target value is lesser or greater than the current node's. If it's lesser, we move to the left child, and if it's greater, then we move to the right. Either way, we'll call removeNode again using our child node. And we'll recursively continue this search cycle until there's a match.

Finding a Match: Delete Node with One or No Children

const removeNode = (node, value) => {
  // previous code

  if (value == node.value) {
    // the node is a leaf,
    if (!node.left && !node.right) { 
      // delete the node
      return null; 
    }

    // if there isn't a left child,
    if (!node.left) { 
      // then replace node with right child
      return node.right; 
    }

    // if there isn't a right child,
    if (!node.right) { 
      // then replace node with left child
      return node.left; 
    }
  }
}

Now, let's focus on what to do when there's a match. First, we'll check if the node has any children. If it doesn't, that means it's a leaf node and we can safely delete it by giving it a value of null.

But if the node does, in fact, have one child, then we can replace it with its child node.

At this point, we've covered all the simple steps of deleting a leaf node and replacing the node with the only available child.

Finding a Match: Delete Node with Two Children

And now this is where it gets fun. And by fun, I mean messy. Maybe you'll want to take a brief brain break before we continue.

  const removeNode = (node, value) => {
    // previous code
    if (value == node.value) { 
      // previous code

      // assigning right child node to temp
      let temp = node.right; 

      // while there is a left child,
      while(!temp.left) {
        // traverse along left branches 
        temp = temp.left;
      }

      // replace node value with temp value
      node.value = temp.value;
      // delete leaf
      node.right = removeNode(node.right, temp.value); 
    }
  }

Continuing the logic from here, we're assuming that the node has two children, but we're only going to work with the right child subtree.

From the root of this subtree, we're going to traverse all the way down the branch, as far left as we can go until we reach a leaf. When we reach that destination, we replace the node value with the leaf (temp) value.

Great! We've successfully deleted the target value from the node by replacing it with another already existing value.

But we're not done! Now we need to delete the leaf node so that we're not left with doubles of the same value.

We'll call the function removeNode again, this time to remove the leaf node value of the same right child subtree.

And now, we're done.

Here's the full code.

remove(value) {
  const removeNode = (node, value) => {
    if (!node) {
      return null;
    }

    if(value == node.value) {
      if (!node.left && !node.right) {
        return null;
      }

      if (!node.left) {
        return node.right;
      }

      if (!node.right) {
        return node.left;
      }

      let temp = node.right;

      while(!temp.left) {
        temp = temp.left;
      }

      node.value = temp.value;

      node.right = removeNode(node.right, temp.value);  

    } else if (value < node.value) {
      node.left = removeNode(node.left, value);
      return node;

    } else {
      node.right = removeNode(node.right, value);
      return node;
    }
  }
  this.root = removeNode(this.root, value) 
}

Conclusion

That's it for now with BSTs and object methods. Next week, we dive into Binary Tree Traversals!

For more information on binary trees, check out these other blogs from my 5-part binary tree series!

Binary Trees (Part 2) - Binary-Search Trees are the BeST

Jenny Shaw — Mon, 18 Nov 2019 16:48:03 +0000

In this blog, I'll be covering Binary-Search Trees, focusing primarily on BST structuring, how to create a BST class, insert new nodes, and check for a value in Javascript.

What are Binary-Search Trees?

Binary-Search Trees (BSTs) are a binary tree data structure that come with a special quality -- sortedness.

A BST is naturally sorted, which makes searching for a value extremely efficient and quick. And the BST class possesses methods to insert and delete nodes in ways that always preserve and maintain that sorted state.

Nodes in a binary tree can point to no more than two children. In a BST, however, there are additional supreme rules about a node's location in relation to other nodes, and this is to maintain the hierarchical order of the tree.

Each parent node points to a left child and/or a right child. If a child's value is less than the parent's, the child must be the left child node. On the other hand, if the child's value is greater, then that child must be the right child node.

Code Break: Node and BST Classes

Let's build out the basic pieces of a BST in Javascript.

First, we'd write out a Node class. A node would have a value property which contains the value used as we initialize a node object. It would also have references to a left node and a right node, both of which will be null since at the moment of its creation it'll just be a standalone node.

class Node {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

To start building out the tree, we would also create a BST class. The class would contain a reference to the root, and because a new tree begins with a new node, the root would be the first newly initialized node.

class BST {
  constructor(value) {
    this.root = new Node(value);
    this.count = 1;
  }
}

You might've noticed that I also added another property to BST called count. It refers to the number of nodes existing in the tree, and it'll be useful when you want to keep track of your node count as you're inserting or deleting nodes.

BST Method: Node Insertion

So, in the event that we want to insert a new node into a tree, we have to consider its value. A new node's value determines our path through the tree's branches all the way to the very end. It a potentially zigzagging journey all the way to the bottom.

At every node that we visit, the new node compares its own value with the currently visited node to determine whether we should follow the left or right path from there. If the new node's value is smaller, we'll travel further left, or if it's larger, then we'll travel further right.

And finally, when we reach a node where the next direction we'd want to follow points to null, we then point the current node to our new node and complete the insertion.

Code Break: Insert Method

Inside of the BST class, following the constructor, we'll create a method called insertNode which will do what we just described above.

First we'll initialize the new Node that we want to insert.

// insert method inside of BST class
insertNode(value) {
  let newNode = new Node(value);
  this.count++;
}

Then, we need a helper method, search, to help us with two tasks.

The first is to search for the appropriate path from the current node to the next -- in other words, it chooses whether we go left or right.

The second is to determine if there's a node following that path. If there isn't, the search inserts the new node by pointing the current node to it. However, if there is, we'd continue in that direction and visit the next node where we start the search cycle all over again.

This search cycle can be accomplished recursively.

// write search helper method inside of insertNode() method

const search = node => {
  //if the new node value is less than the current node value, we'll look left
  if (value < node.value) { 
    // if there's no left child,
    if (!node.left) { 
      // then insert the new node
      node.left = newNode; 
    } else { 
      // search the left node by calling the method on it 
      // (yay, recursion!)
      search(node.left); 
    }
  // if new node is greater than current node, we'll look right
  // repeat similar logic
  } else {
    if (!node.right) {
      node.right = new Node;
    } else {
      search(node.right)
    }
  }
}

To wrap the insertNode method up, we'd call search on the root. This starts the search beginning on the root and then on every node that we visit thereafter.

// at the end of insertNode method...

search(this.root);

Here's the entire method in a single snippet.

insertNode(value) {
  let newNode = new Node(value);
  this.count++;

  const search = node => {
    if (value < node.value) { 
      if (!node.left) { 
        node.left = newNode; 
      } else { 
        search(node.left); 
      }
    } else {
      if (!node.right) {
        node.right = new Node;
      } else {
        search(node.right)
      }
    }
  }
search(this.root);
}

BST Method: Checking if a Tree Contains a Value

Now let's see if we can find target values!

If I were to search for a value in a BST, it'd super quick. Even in your worst-case scenario, it wouldn't even have a time complexity of O(N) (meaning that you had visited and processed every single node on the tree) but of O(log N). You would never have to process more than half of the values in a tree to find your target.

Remember when I mentioned that the left child always has a smaller value than the parent, meanwhile the right child has a greater value? Because it's set up this way, every time I compare the value I'm searching for with a node and as soon as I've decided whether to visit the left or right subtree, I've essentially discarded the other half of the tree. And each time I do this on a new node, I'm discarding my remaining search pile by half, thus saving significant time and effort.

Below is an example of a successful search for the target value on a tree.

And below here is how we search and conclude that the target value doesn't exist.

Code Break: Contains Method

First, we start our search from the top of the tree. We'll want to establish a current node, a marker to help us keep track of our location on the tree as we travel down it. We'll start the marker at the root by assigning this.root to current.

Then we'll do two things. First, we'll compare the target value to the current node value and see if they match. If they do, we return true, and we're done! If they don't match, then we'll do the second thing, move down the tree one node. If the target value is less than the current value, then we'll move on to the left node by assigning the left node to current. Otherwise, the right node is current. When the loop is complete, we'll repeat the process on the following node. If we've searched the tree from top to bottom with no success, then we break out of the loop and simply return false.

// add a new method to BST class

contains(value) {
  let current = this.root;

  while(current !== null) { // while there is a current node
    // compare values

    // is it a match?
    if (value === current.value) { 
      return true;

    // if not, move down a node
    } else if (value < current.value) {
      current = current.left;
    } else {
      current = current.right;
    }
  }
  return false;
}

Conclusion

Binary-Search Trees are one of the most satisfyingly useful and efficient data structures. Once you understand the structure, they're rather intuitive and easy to understand. And because they're already sorted, they're excellent for searches, insertions, and deletions. Deletions are a little more complicated than the methods I covered here, so I'll be writing more about it in the next blog. Stay tuned!

For more information on binary trees, check out these other blogs from my 5-part binary tree series!

Binary Trees (Part 1) - The Basics

Jenny Shaw — Wed, 13 Nov 2019 21:10:09 +0000

After a few surprise encounters with binary trees last week, I thought it'd be good for me to finally get more familiar with them so that later I can tackle binary tree problems with more confidence and less angst.

This is simply an introduction to trees and the different parts that make up the structure. I also touch on what various binary tree structures can look like and why trees, especially binary trees, are applicable and useful.

What are Binary Trees?

Behold, a perfect specimen of the tree data structure in its natural habitat, shot by Marty Kugler

A tree is a data structure that looks like an upside-down tree consisting of nodes. A binary tree is a structure of nodes that each point to no more than two children.

The Physiology of a Tree

A tree is a structure composed of nodes that each contains a value or data. The root is a single node located at the top of the tree. It is the start of the tree where nodes point to child nodes connected by branchlets called edges. A subtree, much like a clipping, is a subsection or part of a tree.

The root of this tree is the parent of two child nodes, each either a left or a right child. Two children or sub-trees of a shared parent are siblings. It's possible for a child to also be the parent of two other child nodes further down the branch.

As we follow a branch down from a parent node, any other node located down that branch is its descendent. And if we follow a branch upwards from a child node, any node up that branch is an ancestor of the child node.

At the bottom or terminal of a branch is the leaf or external node, which has no children. Nodes that branch further to one or more child nodes are branch or internal nodes.

Describing a Binary Tree

When we describe a binary tree, we can discuss its height or its depth.

When we talk about a node's depth, we're specifying how many branches or levels down a node is from the root.

However, when we talk about height, we can either describe the height of a node or the height of the tree. In both cases, we're describing the distance from an external node to the node or root.

Binary Tree Identification

Binary trees can be structured differently and possess different kinds of characteristics or qualities.

A full or strictly binary tree is structured so that every node possesses either two or no children.

A complete binary tree is a tree where nodes at every level but the last is required to have two children. On the last level, the children are positioned as far to the left as possible. So, complete binary tree nodes are connected from top to bottom, left to right.

A perfect binary tree is both full and complete. All the leaf nodes are located at the same depth, and all internal nodes have two children.

A balanced binary tree describes a tree where two sibling subtrees don't differ in height by more than one level. If the difference in height is greater than that, then it is unbalanced.

If every node in a tree has only one child, the structure is a degenerate or pathological tree, and is essentially a linked list.

Why are Binary Trees Useful?

Like the family trees many of us are familiar with, trees are hierarchical and can represent structural relationships in the data. More technological examples and applications of trees can be the DOM or your file directory.

Binary Search Trees (BSTs) are especially useful in algorithms because they are naturally sorted, which makes search, insertion, and deletion of values especially quick and efficient. This is definitely worth diving into in another blog post!

For more information on binary trees, check out these other blogs from my 5-part binary tree series!

Reversing a Linked List

Jenny Shaw — Mon, 14 Oct 2019 14:51:55 +0000

A Linked List Problem

I'm learning about Linked Lists and trying my hand at my first linked list problems. Here's a basic one that I want to focus on today.



Task: Reverse a singly linked list.

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output: 5 -> 4 -> 3 -> 2 -> 1 -> NULL

Failed First Tries

Remember the last time I blogged about reversing strings and integers? I mentioned then that the first time I attempted an integer reversal, I approached it the same way I did with strings and arrays, which didn't work out as great as I would've liked. As per my usual habit, I made a similar mistake here with reversing a linked list.

I started by thinking I'd use the old 'pop' and 'push' approach and realized almost immediately that that just wasn't going to work with this data structure. With singly-linked lists, just to pop or remove the last node would involve traversing the entire length of the linked list, from head to tail, one node at a time. And then, there was a second partial journey to consider. Starting once again from the head of the list, I'd have to re-traverse until I found the appropriate place to re-insert the node. That means, for each and every node I wanted to move, I had to traverse the list at least one and a half times, and that could take forever if your list happened to be just a few nodes too long. It seemed an awfully redundant approach that just didn't make great sense. I was sure there was a better way to go about it.

And there was. Unfortunately, though, I didn't quite figure it out on my own. Ah well.

After about a half-hour of honest effort, I looked up the solution, which I admittedly couldn't understand, but later also found a great video explanation by Back to Back SWE that helped clarify my confusion.

A Step By Step Solution Explanation

The video covers two solutions, one iterative and the other recursive, but I'm just going to focus on explaining the iterative solution for now.

I'll set this explanation up in three stages:



function reverseList(head) {
  // Stage 1: The Setup
  let prev = null;
  let curr = head;
  let temp = null;

  while (curr != null) {
    // Stage 2: The Reversal
    temp = curr.next;
    curr.next = prev;

    // Stage 3: The Shift (Variable Reassignment)
    prev = curr;
    curr = temp;
  }

  return prev;
}

Stage One

In the first stage, I'll have three variables:

curr to keep track of the current node starting at the head of the list,
prev to track the node previous to the curr and is null only for now because there's no attached node prior to curr at the moment, and finally...
temp, a temporary container for the node curr presently points to. I won't assign anything to it just yet, so for now, it'll be null.

Stage Two

At the second stage, we'll open a while loop, during which we'll be re-arranging the nodes.

Keep in mind that with every loop, curr is going to move up the nodes in the list. As curr moves forward node by node, it'll eventually reach null, the end of the list, and that will break the while loop.

At the first line of the loop, we'll assign curr.next, the node following curr, to our variable, temp.

It is temp's job to help us keep that particular node and the connecting nodes thereafter safe and within reach. Why is that important? Because we're about to sever that node from curr, and we don't want to lose it.

On the following line, by assigning prev to curr.next, we direct curr's only pointer towards prev, thus breaking the link to what used to be our old curr.next node as well as the rest of the list.

Good thing we were prepared and kept that node secured in temp!

Stage Three

One last thing before we complete this loop. In preparation for the next loop, we have to shift our variables over by one node. The current node is now prev, and curr is the head of our severed list in temp.

You might notice that we now essentially have two separate lists,
1 -> NULL and 2 -> 3 -> 4 -> 5 -> NULL. But no worries because as we continue looping, we're going to rejoin them node by node until the reversed list is complete.

Some Thoughts

When I finally understood the solution, I felt like my mind was blown. It's really not that complicated a problem or a solution, but as the process of the algorithm was drawn out, there became significant shift in my perspective. As I watch the reversal step by step, I realize that all that's being done here is not the rearrangement of the nodes into reverse order, but the reversal of direction in the linked list. I've been so focused on the order of nodes, looking at them like in an array, that I wasn't looking at the pointers and the role they played in the data structure. I'd completely overlooked that simply redirecting the pointer could've achieved the same thing.

There's really no difference between NULL <- 1 <- 2 <- 3 <- 4 <- 5 and 5 -> 4 -> 3 -> 2 -> 1 -> NULL, but for me, seeing the list rotated just 180 degrees changed the way that I perceived linked lists, and I think that it helps me be more flexible in the ways that I approach them in the future.

I hope these illustrations I created made it easier for you visualize, understand, and replicate this solution to the problem too!

Blog References

Linked Lists, Victor S.Adamchik, CMU, 2009
How To Reverse A Singly Linked List | The Ultimate Explanation (Iteratively & Recursively), Benyam Ephrem, Back to Back SWE, 2018
Reversing an Integer Mathematically, Jenny Shaw, dev.to, 2019

Other Helpful Videos

Reversing an Integer Mathematically

Jenny Shaw — Wed, 09 Oct 2019 20:37:12 +0000

The Problem

This an algorithm problem I've encountered a couple of times called Reverse the Integer.

Write a program or function called reverseInteger 
to reverse the order of digits of a given integer.

Input: 12345
Output: 54321

At first glance, it appeared easy enough to figure out. One of the first problems I ever remember having to solve was Reverse the String, and so, because the two seemed similar enough, I figured I could use the same approach for both.

Reverse the String

Here's one solution to Reverse the String:

function reverseString(str) {
  let reversedStr = '';  // initialize variable with empty string

  for (let i = str.length - 1; i >= 0; i--) {  // iterate backwards through each character of str (input)
    reversedStr = reversedStr.concat(str[i]);  // add each character to end of reversedStr
  }

  return reversedStr;  // after completion of iterations, return reversedStr
}

reverseString('dog')
// returns 'god'

Here, I plan to return a variable called reversedStr at the end of my function. First, I initialize it as an empty string, and as I iterate backwards through each character of str, the original string input, I take that character to build up reversedStr using concatenation. Almost like .pop() and .push() in an array situation.

Reverse the Integer (like a string)

We could reverse integers using a similar algorithm, but there are a couple of caveats:

integers can't be iterated through, and
digits can't be concatenated.

If our input for reverseTheString() were an integer, the function would just spit back an empty string. Useless.

To resolve this, we'd have to first convert the integer input into a string before iteration and concatenation. And if we're expected to return an integer in the end, we'd also have to convert the string back into an integer before returning the value.

function reverseInteger(num) {
  let numStr = num.toString();  // <-- convert integer to string
  let reversedNumStr = '';

  for (let i = numStr.length - 1; i >= 0; i--) {
    reversedNumStr = reversedNumStr.concat(numStr[i]);
  }

  let reversedInt = Number(reversedNumStr); // <-- convert string back to integer
  return reversedInt; // return a reversed integer
}

reverseInteger(12345)
// returns 54321

I've never been very enthusiastic about reversing an integer like a string for a few reasons.

Although this function certainly gets the job done for (most) integer inputs, I don't like having to go through the extra trouble of converting data types back and forth. I'd rather stick to just one data type.

Also, we're asked to reverse integers, yet we're largely manipulating strings, so this feels like a rather tangential approach, a little like a cheat. And I'm no cheater, so we're going to learn to do this right.

Reverse the Integer with Math

Let's approach this problem instead in a way where we can still cleanly 'pop' and 'push' digits, do it all mathematically, and completely avoid the need to convert our integer into a string and back.

(By the way, if you're worried about the math, don't be. We're sticking with basic arithmetic here. Elementary school level stuff. If you understand subtraction, multiplication, division, and place values, then you've got this, kid.)

Keep in mind that in this function, we'll be handling two variables. The first, num, is the input from which we'll be 'popping' digits until there are none left. The second, reversedInteger, will be our output. Here we'll be building up the reversed order of digits by 'pushing' on the 'popped' digits from num.

Step 1:

We'll start with the variable, reversedInteger, and initialize its value at 0.

function reverseIntegerWithMath(num) {
  let reversedInteger = 0; // <-- initialize reversedInteger

}

Step 2:

We're going to start a while loop and continue it while num still has a value greater than 0. Every loop, we'll be chipping away one digit from num and using the digit to build reversedInteger.

function reverseIntegerWithMath(num) {
  let reversedInteger = 0;

  while (num > 0) { // <-- open while loop



  }
}

Step 3:

At the beginning of each loop, we'll multiply reversedInteger by 10.

function reverseIntegerWithMath(num) {
  let reversedInteger = 0;

  while (num > 0) {
    reversedInteger *= 10; // <-- set up for proper place value


  }
}

// Let's keep track of what num and reversedNumber look like 
// starting from here...

// num => 1234

// reversedInteger => 0 * 10 
//                 => 0

Step 4:

Now, let's take our num and divide by 10 using the modulo operator. This is to find a single-digit remainder which equals the current last digit of nums. We'll initialize a variable called rem at the top of our function, and tuck that value safely into it.

Then subtract rem from num and divide the result by 10. And now we're left with the same integer, but one digit less.

POP!

function reverseIntegerWithMath(num) {
  let reversedInteger = 0;
  let rem = 0;               // <-- initialize remainder

  while (num > 0) {
    reversedInteger *= 10;
    rem = num % 10;          // <-- remainder grabs last digit
    num = (num - rem) / 10;  // <-- eliminate zero in num
  }
}

// rem => 1234 % 10 
//     => 4

// num => 1234 - rem 
//     => 1230 / 10
//     => 123

// reversedInteger => 0

In case you're curious...
Why are we dividing and multiplying numbers by 10?

It's because we're replicating decimal place values where each place has a value of times ten from right to left.
Dividing by 10 eliminates the last zero in num, which then gives us access to the next digit that ends up in the ones place.
Multiplying reversedInteger by 10 makes room in the ones place where we can place the digit we popped off from num.

Step 5:

Next, it's time to "push" the "popped" digit from num by taking the remainder and adding it to reversedInteger.

PUSH!

function reverseIntegerWithMath(num) {
  let reversedInteger = 0;
  let rem = 0;

  while (num > 0) {
    reversedInteger *= 10;
    rem = num % 10;
    num = (num - rem) / 10;

    reversedInteger += rem;  // <-- 'push' remainder onto end of reversedInteger
  }
}

// rem => 4

// num => 123

// reversedInteger => 0 + 4
//                 => 4

Step 6:

We've completed one cycle of this process. Repeat until num's value dwindles to 0 and there are no more digits to 'pop' or 'push'.
After the reversal of digits is complete, we can finally return reversedInteger.

function reverseIntegerWithMath(num) {
  let reversedInteger = 0;
  let rem = 0;

  while (num > 0) {
    reversedInteger *= 10;
    rem = num % 10;
    num = (num - rem) / 10;

    reversedInteger += rem;
  }

  return reversedInteger;  // <-- done!
}

// if you want to see what happens in the next loop
// num => 123 - 3 (step 4)
//     => 120 / 10
//     => 12 [pops the 3 from original integer]

// rem => 123 % 10 (step 3)
//     => 3

// reversedInteger => 4 * 10 (step 2)
//                 => 40 + 3 (step 5)
//                 => 43 [pushes the 3 onto reversedInteger]

This is a pretty simple and neat trick in numeric manipulation and a much-improved approach to the reverseInteger problem. I'm always looking for other creative ways to solve simple problems like this, so if you've got clever ones to share, drop them in the comments!