DEV Community: Blake K

Creating/Securing a Remote Dev Environment

Blake K — Mon, 07 Jun 2021 15:18:19 +0000

Introduction

A remote development environment is an environment/server hosted externally (i.e. not on your local machine) that you connect to remotely to perform your development work on.

Using the Remote-SSH extension on Visual Studio Code, you can develop on a remote machine while maintaining the feel and responsiveness of developing on your local machine.

Image Source: Visual Studio Code / Microsoft

The way this is achieved is via a SSH Tunnel. But you can secure this a step further by requiring proof of identity via an SSO Identity Provider (like Google, Github, Facebook, Active Directory, etc) by using Cloudflare Access and Cloudflare Tunnel.

There are numerous benefits to using a remote environment to perform your development on. Here's just a few:

You can switch machines without losing your work. Since your work is not on your local machine, that means that you can switch from your desktop to your laptop and not lose anything.
You can develop your application/system on an environment that closer replicates the environment that your product will be deployed to.
There's less of a security risk if your local machine is lost/stolen. Your code/files aren't on there.
Colleagues and other developers can also connect to your remote development environment to help debug or perform any other necessary work.

Goals

By the end of this tutorial, you will have:

A DigitalOcean droplet setup with your development stack
Visual Studio Code setup locally with the Remote-SSH extension
The cloudflared daemon installed both on your remote and local machines
An SSH config on your local machine to easily connect to your remote machine using Cloudflare Tunnel and Cloudflare Access

Prerequisites

A generated SSH Key
- You will need to upload your public key to DigitalOcean
- You will need your private key in order to SSH into your Droplet initially
A DigitalOcean account
- New users can use the link above to get a $100 credit valid for 60 days when you add a payment method to your account
A Cloudflare account with a domain added
- This domain will be used by you to connect to the remote machine
A Cloudflare for Teams account already setup
- A free plan is available
A SSO Integration already setup within Cloudflare for Teams
- In this tutorial I'm using a GSuite integration to verify my identity
Visual Studio Code installed on your local machine

Step 1 — Configuring Cloudflare

You will create an access policy for your selected domain.

Cloudflare Tunnel is a service which provides a secure connection between the nearest Cloudflare datacenter and your remote machine, without opening public ports. This tunnel is how you will connect to your remote machine securely. Previously this was a part of Cloudflare's paid Argo service, but as of April 2021 has been made free of charge.

From your Cloudflare dashboard, select the domain (or zone) that you have chosen to use for this tutorial.

You need to create an access policy. This policy will determine who has access to your Droplet.

Click on the access tab on your domain's Cloudflare dashboard. Scroll down to Access Policies and hit Create Access Policy.

Give an application name, and the subdomain that you will use to connect to your Droplet (decide this now, you'll need it again later in this tutorial). For session duration, decide how long a session should be valid for.

You need at least 1 policy. Create one by giving it a name. Then add an include-rule. For this tutorial, I decided on "emails ending in" and the domain of my GSuite account.

Once you're done, hit save. Now that your Cloudflare settings are configured, it's time to create your remote machine.

Step 2 — Creating your Droplet

You will create a Droplet on DigitalOcean with a new user, your preferred tools/programs, and the cloudflared daemon.

To begin, visit this link to access the Droplet creation page.

For this tutorial, you will use Ubuntu 20.04 as your operating system.

For the Droplet plan select the configuration that you think you will need for your development work. From personal experience, the Regular Intel, 4GB / 2 CPUs plan works great on a stack with Java 11, Apache Maven, Git, and Docker.

Next, select your preferred datacenter. Typically, the datacenter closest to you is the best option to minimize latency.

For additional options, enable IPv6 and User data. Monitoring is optional but recommended if you wish to view stats about your Droplet online.

A text field will appear after selecting the user data checkbox. This is where you will paste a script to be executed when the server initially boots for the first time.

Below is a script that I have provided for you to use. It creates a new user, optionally installs some packages, and installs cloudflared. There is a variable for the name of the user to create.

Back to the Droplet creation panel - For authentication select SSH Key and upload your public SSH key if you don't already have a key uploaded.

The remaining options are optional. I recommend changing the hostname to something you recognize, such as the domain name that you plan on using for that Droplet.

Once finished configuring your options, press Create Droplet. You've just created your remote machine! The next step is to configure it and ensure it is secure.

Step 3 — Securing your Droplet

You will configure the cloudflared daemon and setup the SSH tunnel on your Droplet.

On the DigitalOcean panel, navigate to your newly-created Droplet. Copy the public IPv4 address listed.

You are going to have to SSH into your Droplet with the username that you configured in the script provided. To do this, on your local shell run ssh <your configured username>@<copied IP address> -i <path to your private SSH key>.

An example might look like ssh sammy@XXX.XXX.XXX.XXX -i ~/.ssh/id_rsa.

Navigate to /etc/cloudflared/ using cd /etc/cloudflared.

Before proceeding, ensure that cloudflared is up-to-date. Run sudo cloudflared update.

Next, you need to authenticate cloudflared with your desired zone (domain).

Run cloudflared login. It should output a link, which you can then copy to your web browser and load.

On the website, it is important that you select the zone that you will be using to connect to the Droplet with. Click Authorize. You can close that website once done.

Return back to your SSH session. You now need to move the newly-downloaded certificate to /etc/cloudflared/cert.pm. Do this by running sudo mv /home/sammy/.cloudflared/cert.pem /etc/cloudflared/cert.pem, replacing sammy with your configured username.

Now is the time to create the tunnel.

Do this by running cloudflared tunnel create NAME, replacing NAME with a label for your tunnel. An id should then be printed out after running the command. Make note of it.

Next, you need to create a configuration file telling cloudflared what to do when it runs.

Modify and copy the provided config file below. Replace XXX with the id of your created tunnel, and YOUR.DOMAIN.HERE with the hostname that you wish to use to connect to your Droplet. The apex domain must match the one you selected when authenticating cloudflared.

Create the file /etc/cloudflared/config.yml by using your favorite text editor (such as vim or nano) and pasting your modified config template from above.

To create the DNS record for your configured domain name, run cloudflared tunnel route dns <id> <subdomain> where id is the id of the tunnel, and subdomain is the subdomain you selected in your config file. You can verify on your Cloudflare DNS page that a CNAME record was created.

The cloudflared daemon is now fully configured. It's time to start it! It's best to run the daemon as a service.

Run sudo cloudflared service install and sudo service cloudflared start.

To verify that there were no errors in the service starting, run sudo service cloudflared status. You should see the tunnel being started with some connections being made. Those connections are to nearby Cloudflare datacenters.

With your remote machine configured, it's now time to configure your local machine so it is able to connect to your Droplet over this secure tunnel.

Step 4 — Configuring your local machine

You will configure your local machine to use the Cloudflare Tunnel when SSHing into your Droplet, and install the Remote-SSH extension in Visual Studio Code to be able to modify files on your Droplet seamlessly.

Install cloudflared on your local machine. You can view full instructions from Cloudflare's website. It supports Mac, Linux, Windows, and Docker. Again, it's best to run the daemon as a service.

You do not need to authenticate the daemon on your local machine (i.e. do not run the login command).

Now, you need to update your local SSH config to make use of cloudflared for your Droplet. The daemon has a feature which will generate most of this config for you.

Run cloudflared access ssh-config --hostname YOUR.DOMAIN.HERE, replacing the variable with your domain that you put in your config on your Droplet.

Determine where your local SSH config is. On Mac, it's located at ~/.ssh/config.

It should print something out like this to add to your SSH config:

Host YOUR.DOMAIN.HERE
  ProxyCommand /usr/local/bin/cloudflared access ssh --hostname %h

Note, the path in your proxy command may be different depending on your operating system. That's why its important to use what the program gave to you after running the command.

Append the printed text to your local SSH config using your preferred text editor. Add an additional line under the Host labeled User with your Droplet's username (see below for an example). This makes it easier for Visual Studio Code.

Host YOUR.DOMAIN.HERE
  ProxyCommand /usr/local/bin/cloudflared access ssh --hostname %h
  User sammy

Try connecting to your Droplet using this updated SSH config. Run ssh YOUR.DOMAIN.HERE. If all goes well, your browser should open prompting you to select an identity provider, you login, and authorize the request. Once authorized, your local terminal will SSH into your Droplet and you can close the opened webpage.

Now it's time to setup your local Visual Studio Code IDE. Open VS Code and install the Remote-SSH extension.

Once installed, by default the extension should show remote targets from your local SSH config file. You can select your newly-added target to connect to it.

You can also use the opensshremotes.openEmptyWindow VS Code command to select a remote target.

After authentication (or if your session is still valid from your test), VS Code will connect to your Droplet and automatically install the VS Code Server (first boot only).

From here, you can install extensions onto your Droplet, create directories/files, and even open a terminal in VS Code.

Conclusion

Remote development environments are a great way to work. They allow you to develop and test your product in an environment closer to production, permits switching machines, and allows multiple people access to the environment. Using Cloudflare Access and Cloudflare Tunnel, this access can be granted or denied based on authentication through SSO providers, providing a clean way to authenticate and authorize users.

DNS Explained. Resolution

Blake K — Sun, 24 Jan 2021 19:54:43 +0000

This is an article in the DNS Explained. series. Click here to read the introduction post.

Resolution is the process of asking for the resource records of a fully-qualified domain name (FQDN) and receiving back an answer. Every time that your computer does not have an IP address cached for a required FQDN, a resolution takes place. In this post, I discuss the main components involved in DNS resolution and explain the two main methods in which resolution is performed.

Components

There are five main components that play a role in DNS resolution.

The first component is the client. This is the host that is asking the question, "Where is www.netflix.com on the internet?"

The second component is the DNS resolver. Typically provided by your ISP, this serves as the first component that the client reaches out to if the answer to the DNS query is not cached by the client. Its role is to query the other components to find the answer to the original question. The way it does this depends on the type of DNS resolution being performed.

Clients can configure their settings to use a DNS resolver not provided by their ISP. Google, Cloudflare, Verisign, and Cisco are just a handful of companies that offer free-alternative DNS resolvers. Be aware of which resolver you choose though! Every site you visit will likely send a DNS query which is handled by your chosen DNS resolver. This gives that resolver an ability to see what you request and may sell this data to advertisers. Always read the policies of DNS resolvers that you are considering to use.

The third component is the DNS Root Zone, which is questioned if the DNS resolver does not have the answer in cache. Its role is to return the nameservers for the requested TLD. There are 13 root servers in the world operated by 12 organizations. These servers are anycasted and I go into more detail about them in my DNS Architecture post.

The fourth component is the TLD's Nameservers. Its role is to return the authoritative nameservers of the requested second-level domain.

Finally, the fifth component is the Authoritative Nameservers. These servers are the responsibility of the registrant to provide, and their role is to return the resource record for the requested third-level domain (or apex domain).

Iterative Resolution

There are two types of resolution, the first is iterative. In an iterative resolution, it is the responsibility of the DNS resolver to keep querying nameservers until it gets an answer.

Let's go through each step in more detail.

The client sends an iterative DNS query for www.blakes.site..
The DNS resolver receives this query. If it doesn't have an answer for this query already cached, it will continue by asking a root server where the nameservers for .site are. If it is cached, the answer will be returned here and the process will terminate. Sidenote: The DNS resolver could also store cache entries for the .site TLD nameservers and the blakes.site authoritative nameservers and skip the appropriate steps.
The root server returns the IP addresses for the .site nameservers. It also can cache the .site nameservers for future usage.
The DNS resolver now has to ask the .site TLD nameservers for the IP addresses of the blakes.site authoritative nameservers. It also can cache the .site nameservers for future usage.
The .site TLD nameservers return the IP addresses for the blakes.site authoritative nameservers. The DNS resolver can cache the blakes.site authoritative nameservers for future usage.
The DNS resolver asks the blakes.site authoritative nameservers for the resource records for the entry www.
The blakes.site authoritative nameservers return the resource records for the entry www.
The DNS resolver caches the response and returns it back to the client.

Recursive Resolution

The alternative to iterative resolution is recursive resolution. Instead of an address to the next nameserver being sent back to the DNS resolver to then query, the nameserver makes the request itself and returns the result all the way back up to the DNS resolver.

Let's also go through this resolution step-by-step.

The client sends a recursive DNS query for www.blakes.site.. Nothing new.
The DNS resolver receives this query. If it doesn't have an answer for this query already cached, it will continue by asking a root server for the answer to www.blakes.site.. If it is cached, the answer will be returned here and the process will terminate.
If the root server did not have an answer cached, then it asks the next component that could have an answer: the TLD nameservers. The root servers can also cache the TLD nameservers for the requested domain for future use.
If the TLD nameservers did not have an answer cached, then it asks the next component that could have an answer: the authoritative nameservers. The TLD nameservers can also cache the authoritative nameservers for the requested domain for future use.
The authoritative nameservers find an answer for www.blakes.site. and pass the answer up back to the TLD nameservers.
The TLD nameservers pass the answer back up to the root server.
The root server passes the answer back to the DNS resolver.
The DNS resolver caches and passes the answer back to the client.

There is caching at each component, so it is possible that only a partial resolution has to take place for a query. If the requested FQDN is popular and the DNS resolver is being used by a lot of people, then it is completely possible that the root servers are never contacted.

Recursive Resolution: Pros/Cons

In general, recursive resolution tends to be faster than its iterative counterpart due to caching of final answers. However, this type of resolution creates security flaws including cache poisoning and DNS amplification attacks.

Responsibility: Recursive vs Iterative

In recursive resolution, the burden of having to contact nameservers belongs to the server. On the flip side, for iterative resolution, the burden of contacting nameservers belongs to the client.

DNS Resolver Observation

It should be noted that for both recursive and iterative resolution, it is required that the DNS resolver already know the IP addresses of the 13 root servers. Implementation wise, these addresses are simply hardcoded and publicly available.

DNS Explained. The RRR Model

Blake K — Sun, 06 Sep 2020 04:05:01 +0000

This is an article in the DNS Explained. series. Click here to read the introduction post.

DNS isn't all technical. At its core, there is a lot of policy and thus jargon created. The intent of this post is to clear up some of the most commonly used jargon relating to entities in DNS.

There are three main stakeholders in the DNS ecosystem. Together, they form the RRR (triple-R) Model.

Registrants are the individuals and organizations that register a domain name.

They obtain a domain name from a registrar by paying the price that that particular registrar sets. If a potential registrant thinks that a registrar's price is too high, they can look at another registrar (competition!).

If Alice registers the domain name “alice.rocks”, then Alice is considered as the registrant for the domain name “alice.rocks”.

Registrars are third-party organizations that "sell" domain names to registrants.

Domain names are not really sold but rather rented on an annual basis. The maximum length of a registrant’s active registration depends on the policy of the specific TLD, but usually is 10 years.

Registrars are also the bridge between registrants and registries, because they have to interface with the specific TLD's registry to submit the domain creation.

Before registrars were established, a TLD’s registry would act as the registrar. This didn’t permit much competition, so the concept of a registrar was adopted.

Some notable registrars include:

GoDaddy
NameCheap
101domain
Network Solutions

Registries operate the backend infrastructure for a top-level domain and process domain creations, renewals, expirations, deletions, and transfers.

Their customers are registrars, who then sell to registrants. Since registries need to make money too, there is a wholesale cost for new domain creations, among other fees that are charged to registrars.

There is a single registry for each TLD. The organization ICANN designates via contract the sole registry for each TLD.

Some notable TLDs and their corresponding registries are:

TLD	Registry
.com	Verisign
.net	Verisign
.org	Public Interest Registry
.gov	General Services Administration
.coffee	Donuts
.tv	Verisign
.site	Radix
.me	DoMEn d.o.o

Conclusion

Registrants, registrars, and registries make up the RRR model within DNS. Registrants are end-customers leasing a domain name. The organizations that offer the means to obtain a domain name are registrars. Registrars have to communicate with the backend systems of each TLD they want to offer, which are managed by the TLD's registry.

DNS Explained. Hierarchy and Architecture

Blake K — Tue, 28 Jul 2020 16:56:49 +0000

This is an article in the DNS Explained. series. Click here to read the introduction post.

In the first post for this series, I described DNS being both hierarchical and decentralized. In this post, we will dive into what that really means.

DNS is Hierarchical

Hierarchy is obtained through levels of domains, starting at the root server (represented by a period ".").

You may have heard of top-level domains (TLDs) before. Some examples of TLDs include:

.com
.net
.org
.us
.de
.coffee
.ninja

They are called top-level domains because well, they are at the top level (excluding the root)! Organizations can register second-level domains under any valid TLD.

Because DNS is hierarchical, that means that two separate second-level domains can both use the same third-level domain For example, mail.google.com and mail.yahoo.com are both allowed because the uniqueness of the third level domain is limited to the scope of the second-level domain. This was not possible under the predecessor hosts.txt system.

Root Zone Servers

In the above graphic, I introduced a new DNS concept called the root server. The root is the base of the DNS hierarchy tree. While I described it as a single point, it is actually more than that.

In reality, the root server is called the Root Zone servers. It's called the Root Zone because there are actually 13 Root servers. These servers are spread out geographically and are the starting place for traversing DNS via resolution.

ICANN appoints operators for these 13 root servers. There are 12 total operators.

Host name	IP Addresses	Operator
a.root-servers.net	198.41.0.4, 2001:503:ba3e::2:30	Verisign, Inc.
b.root-servers.net	199.9.14.201, 2001:500:200::b	University of Southern California, Information Sciences Institute
c.root-servers.net	192.33.4.12, 2001:500:2::c	Cogent Communications
d.root-servers.net	199.7.91.13, 2001:500:2d::d	University of Maryland
e.root-servers.net	192.203.230.10, 2001:500:a8::e	NASA (Ames Research Center)
f.root-servers.net	192.5.5.241, 2001:500:2f::f	Internet Systems Consortium, Inc.
g.root-servers.net	192.112.36.4, 2001:500:12::d0d	US Department of Defense (NIC)
h.root-servers.net	198.97.190.53, 2001:500:1::53	US Army (Research Lab)
i.root-servers.net	192.36.148.17, 2001:7fe::53	Netnod
j.root-servers.net	192.58.128.30, 2001:503:c27::2:30	Verisign, Inc.
k.root-servers.net	193.0.14.129, 2001:7fd::1	RIPE NCC
l.root-servers.net	199.7.83.42, 2001:500:9f::42	ICANN
m.root-servers.net	202.12.27.33, 2001:dc3::35	WIDE Project

You may be asking yourself, how do hosts and resolvers know about these 13 root servers? The answer is simple: they're hardcoded!

You can view the locations of all the root zone servers here.

DNS is Decentralized

This hierarchical structure of domain levels permits decentralization too. DNS is decentralized in terms of not a single party is responsible for providing the nameservers at each level.

At each second-level domain, there are a set of nameservers. These nameservers are used during resolution to provide the IP addresses of third+ level domains within the scope of that specific second-level domain.

Since the scope is limited to that particular second-level domain, the registry of the TLD does not need to operate this, and instead, the responsibility is given to the second-level domain registrant to provide this functionality.

If the domain registrant does not want the responsibility of providing their own nameservers, there exist third-party companies that offer managed DNS services. Cloudflare is one of the largest managed DNS providers. Most registrars also offer this service.

Observations

We can make a few observations about DNS from the fact that it is both hierarchical and decentralized.

Firstly, DNS is scalable due to its hierarchy. By having "zones" of TLDs, the infrastructure for each zone can be spread out and independently scaled. This is great because some TLDs have more registrations than others.

Secondly, since the hierarchy begins with the root, and the root is represented by a period, the fully qualified domain name (FQDN) technically ends with a period too. This is official and was documented in RFC 1034. You can try it out in your browser and verify that it still works:

smile.amazon.com.
www.google.com.
dev.to./blake

Finally, FQDNs are parsed from right to left. This is because the root starts on the right-hand side, and the lowest level is on the left-hand side.

DNS Explained. Introduction/History

Blake K — Tue, 28 Jul 2020 16:56:24 +0000

Introduction

Imagine this scenario.

Netflix has a lot of fresh content being released. You decide that you want to watch the next season of The Politican. So, you open up your favorite browser, type in netflix.com, and hit enter. Almost instantly, Netflix's profile selection screen pops up.

You probably already know that an HTTP(S) request over a TCP connection is made to Netflix's servers and that Netflix sends back a HTTP(S) response, which is eventually rendered by your browser as the screen you end up seeing. However, a key part is missing here.

In order to make a TCP connection, you need four things:

1) The Source IP
2) The Source Port Number
3) The Destination IP
4) The Destination Port Number

The above four requirements are often referred to as the "TCP 4-Tuple". Now, you already have the source IP and port number, because you are the source! And thanks to IANA, the destination port number is already known based on the protocol used (HTTP: 80/HTTPS: 443).

The only thing missing to make the TCP connection is the destination IP address. DNS is how you obtain it.

Why do we have domain names?

First of all, why do we even have domain names? If we typed the destination IP address, the problem of obtaining the IP address wouldn't exist.

This is correct, but would involve the end-user memorizing the IP addresses of all the sites they wish to visit. You could probably memorize a few IPv4 addresses, but good luck memorizing 5+, or even a single IPv6 address.

Domain names exist so humans don't have to memorize IP addresses. In addition, IP addresses for hosts can change; having a domain name point automatically to the updated address is really handy.

History

Before diving straight into DNS, it is beneficial to know the history of the system and the motivations behind its creation.

The predecessor of DNS was the hosts.txt file for ARPANET (the predecessor of the Internet). This plain-text file was centrally maintained by the Stanford Research Institute and mapped domain names to addresses of computers on ARPANET. Since the number of hosts on ARPANET was under 1,000 at the time, it was a sufficient solution to mapping domain names. However, there were significant drawbacks.

The first drawback is that updates to the file were manually processed by hand. This resulted in long initial delays.

Second, once the original file at Stanford was updated, all hosts on ARPANET also had to have an updated copy of the hosts.txt file. This resulted in propagation times being measured in the span of days. Imagine not having your domain name be accessible for days after you submit an update!

Third, once a domain was claimed, nobody else could have it. If MIT claimed "mail", then George Washington University could not claim "mail". There was no hierarchy, so great domain names couldn't be used by multiple organizations (like "mit.mail" "gwu.mail" which are possible today).

As you can imagine, this simple file "system" wasn't going to cut it for when the future internet comes around with thousands of hosts. A new scalable and automatic system had to be made and put in place.

Defining DNS

Wikipedia defines DNS as, "a hierarchical and decentralized naming system for computers, services, or other resources connected to the Internet or a private network."

I don't know about you, but this definition doesn't really tell me much. Let's reword that a bit.

DNS is a hierarchical naming system that maps strings (called fully-qualified domain names or FQDN) to values called resource records (which can contain a corresponding IP address).

Simply put, you query DNS with a domain name (e.g. www.netflix.com) and DNS will eventually return an IP address back to you. This returned value is the destination IP address needed to complete the TCP 4-Tuple.

Diving Deeper

DNS at its core is a key-value system where the key is a fully-qualified domain name and the value is a resource record. Though DNS has additional components that are vital to the overall health and performance of the system.

We have described a real-life use case for DNS, in addition to briefly going over the need for domains in general, DNS' history and technical definition. Keep reading the "DNS Explained." series to dive deeper into more DNS topics including the RRR model and resolution!

Searching & Sorting w/ Binary Search Trees

Blake K — Fri, 05 Apr 2019 23:29:19 +0000

Introduction

Binary Search Trees are an incredibly useful data structure that holds comparable values in a particular order.

With this particular ordering, it allows for fast lookups and a straightforward way to sort the values in the tree.

Regarding use cases, Binary Search Trees are one of the bases for more abstract data structures such as sets and maps.

Definitions

Before we talk about searching and sorting with Binary Search Trees (BSTs), let's make sure we're on the same page regarding terminology.

A Node holds

A value.
References to other nodes.

A Tree is a data structure that has

One parent node.
Zero, one, or multiple child nodes.
No duplicate nodes.
No node that references previously defined nodes (i.e. no looping).

A tree is implemented as one root node, consisting of children of subtrees that have the properties above.

A parent node is considered as the root node of that specific subtree.
The root node is the starting node for the entire tree.

When you hear the term "Binary Tree", you might feel a little intimidated! But worry not, it's a straightforward concept to grasp.

A Binary Tree is a tree with

At most two child nodes (one left, one right) for any parent node.

Now let's define what this entire post is about - Binary Search Trees.

A Binary Search Tree is a particular type of binary tree where

The left child node is less than the parent node.
The right child node is greater than the parent node.

Implementation

The following code samples are written in C.

We can represent a Node as a structure containing fields holding a value (in this case an integer), and pointers to the left and right child nodes.

// Node Structure
typedef struct node {
    struct node *left; // Pointer pointing to left child node.
    struct node *right; // Pointer pointing to right child node.
    int val; // The value the node is holding.
} node_t;

Sorting

There are different ways that you can traverse a tree. There is pre-order, in-order, out-order, post-order, etc. As this post is specifically about Binary Search Trees, we're not going to go into too much detail about generic tree traversals. However, in-order traversal plays a significant role in BSTs.

In-order traversal follows the pattern LEFT PARENT RIGHT.
Let's take the following BST as an example:

If you traverse the BST using in-order traversal, you'll start with the left node (3), move back to the parent node (5) and end with the right node (7), resulting in 3, 5, 7.

Take a look at that result, does anything stick out to you? In case you didn't notice, it returned a sorted result!

This property of the in-order traversal result is no coincidence.

Try it with any BST; you will always end up with a sorted result. Not convinced? Let's try it one more time with a more complex BST.

Remember that in-order traversal goes like this: Left, Parent, Right.

So starting at 50, go left to 27. 27 has a left child (7), so go there next. 7 doesn't have a left child so that's our first entry. Then move up back to 7's parent (27) which is our second entry, then go to 27's right child (42) which is now our third entry.

So far, our result is:
7, 27, 42

Now, we're done with the subtree where 27 is the root. 50 is the parent of 27, so that's our fourth entry. We then head to 50's right child, 99. However, 99 has a left child (84), so we go there instead. 84 is now our fifth entry. We then go to 84's parent (99) which is our sixth entry. Then we go to 99's right child, which doesn't exist - so we're done!

Our result from the in-order traversal is:
7, 27, 42, 50, 84, 99

Would you look at that, it's completely sorted!

Here's a C implementation of in-order traversal:

void printInOrder(node_t *parent) {
    // Safety Check.
    if (parent == NULL) {
        return;
    }

    // Print Left Subtree.
    printInOrder(parent->left);

    // Print Parent.
    printf("%d, ", parent->val);

    // Print Right Subtree.
    printInOrder(parent->right);
}

In this recursive implementation, we check if the provided Node is NULL or not. This is our base case.

We then recursively call our in-order function on the left child. This will continue calling until there are no more left-children. Then, it will print the current (left) node value. Afterwards, it will again recursively call our in-order function for the right-children.

What we end up with is the values of our provided BST printed out sorted.

Searching

If we want to search for a provided value in a BST, how would we do it?

Searching takes advantage of three features of BSTs:

There are no duplicates.
Values can be compared to each other.
Values to the left are smaller than the parent, and values to the right are greater than the parent.

We start searching at the root node. If the provided value matches the value of the root node, we can simply return because the value has been found.

But if the value isn't a match, we have two options: traverse left or traverse right.

Which should we do?

Well, if the provided value is less than the current node we are looking at, we search left. Otherwise, we search right. This property of having lesser values as the left-child and greater values as the right-child unqiuely defines a Binary Search Tree, so take advantage of it!

In C, this contains function is implemented as so:

bool contains(node_t *parent, const int *value) {
    // Safety Check.
    if (parent == NULL) {
        return false;
    }

    // Found match!
    if (parent->val == *value) {
        return true;
    }

    // Check left subtree.
    if (*value < parent->val) {
        return contains(parent->left, value);
    }

    // Check right subtree.
    return contains(parent->right, value);
}

Not only is this data structure favored for its search efficiency, it's also preferred for its ease of implementation. The search function can be implemented recursively.

As you can see in the implementation, we disregard the right subtree if the value we are looking for is less than that subtree's parent value. Likewise, we disregard the left subtree if the value we are searching for is greater than the subtree's parent value.

Since we either search left or right until the provided value is found, we on average search only half of the nodes in the BST. This makes the average efficiency of searching in a BST O(log n).The worst case is O(n) where all nodes need to be searched (this is where self-balancing trees would be useful).

Full Demo

If you'd like to try out or view the full C implementation demo that includes some testing, click here!

Wrapping things Up

Binary Search Trees are useful data structures when it comes to searching and sorting. By taking advantage of in-order traversal and the properties of this special tree, you can implement both searching and sorting functions not only efficiently, but also easily.

Thanks for reading!