Whether you’re a new graduate with a fresh computer science degree or an experienced software development professional, sometimes it’s good to get a refresh of basic computer science fundamentals. This is especially important when comparing yourself with other software developers, preparing for algorithmic intensive work, or practicing your performance in preparation for a technical interview.
In this article, we’re going to walk through some of the fundamental building blocks of basic algorithmic computer science topics. Just as a warning - this is a long post!
We’ll run through descriptions and examples of a vast array of topics, including algorithm complexity analysis (also called, big-O notation), comparing and contrasting sorting methods such as quicksort, mergesort, and other sorting techniques. We’ll discuss speeding up applications through the use of hash tables. We’ll also walk through combinatorics by creating combinations, permutations, and seeing how to generate all possible pairs from an array. Next, we’ll cover iterative versus recursive functions, including examples of the popular fibonacci and factorial functions.
Now, this is quite a range of topics. However, they’re most certainly important for software developers to understand when designing complex software. Let’s take a look at each topic, starting with the fundamental one, complexity analysis.
Below is a complete list of topics covered in this article:
- Complexity analysis and big-O notation (for-loop examples)
- Sorting. Examples: Quicksort, Mergesort, Insertion Sort, Selection Sort
- Hash tables. Example: Letter occurrences in a string
- Combinations and permutations. Examples: Calculate number of pairs, Find pairs with target product
- Iterative vs recursive functions. Examples: Fibonacci, Factorial
- Binary search and divide and conquer. Example: Searching within a sorted array
- Linked Lists. Examples: Creating a linked list, Reversing a linked list
- Trees. Examples: Creating a tree, Traversing a tree with DFS and BFS
- Breadth-First Search, Depth-First Search, A* Search
- Binary Trees. Example: Inserting, Checking if a value exists, Preorder, Inorder, Postorder traversal. Finding the max depth.
- Binary Heaps: Min-heap, Max-heap
Complexity analysis, also called Big-O notation, is a method for determining the runtime complexity for a particular algorithm. It’s commonly used to gauge the speed or storage requirements for an algorithm. Analyzing complexity can be quite useful, especially when an algorithm requires iterating over many rows of data, possibly performing multiple iterations over child elements and subsets of child elements. The more embedded looping that occurs within an algorithm, the more CPU time that is required for processing the data. As such, an algorithm can slow down dramatically in average or worst-case scenarios, potentially bringing software applications to a crawl.
The reliance on CPU processing time is what makes complexity analysis so important for algorithmic design. Code that operates efficiently and optimally can run far quicker than less optimal implementations. In addition, many of the algorithms and data structures that we’ll cover throughout this article rely on understand complexity analysis to describe the reasons that we use them.
Let’s take a look at the basics behind complexity analysis for various code samples. This will give a general understanding of what we’re looking for when designing algorithms to be efficient and also cover the ground-work for the other topics in this article.
Let’s start with the simplest case for complexity. We’ll simply retrieve the value for a single element within an array or hash.
In the above code, we have an array of 5 elements. Of course, it could also be 5 million elements, but the act of retrieving a single element from it is a very simple and quick operation. We can simply access the value at the particular index within the array. We can perform the same operation with a hash, as well.
The complexity for accessing an array or hash is considered to be O(1).
We describe complexity of an algorithm using the letter ‘O’ followed by a description of the number of iterations. In the case accessing an element within an array or hash, it takes 1 operation to perform. Thus, we can describe the complexity as O(1) for this code example. This is about as good as it gets for algorithm complexity. Of course, while O(1) runtime code is quite fast, it may often come at the expense of storage. This is due to requiring an array, hash, or other storage object for immediately retrieving the key/value pair for a particular piece of data.
Next, let’s look at code that implements a single for-loop.
The code example above contains a simple loop over an array of data. While the array only contains 5 elements, imagine that it could contain 5 million elements. Regardless of the actual size, we can still analyze the complexity to understand how long it can take to run.
In this simple example, we’re iterating over the array a single time and incrementing each value. Since the array contains 5 elements, it will take 5 iterations to complete.
A single for-loop, such as this, runs in O(n) time complexity.
In the simple case of a single for-loop, there are (at worst) 5 iterations. We can simply refer to this as n-iterations. We know the code will always complete after n-iterations, so we can describe the complexity of this code as O(n).
Let’s take a look at a more complex example.
In the above example, we’re now iterating across the array with a nested loop. This is actually a method for retrieving all permutations (including duplicates) of pairings of the data in the array. For example, the nested loop will access elements [1, 1], [1, 2], [1, 3], [1, 4], [1, 5], [2, 1], [2, 2], …, etc.
The complexity for this code is considered O(n^2).
Since the code has a nested loop, it raises the complexity by an order of magnitude. In this case, it will be 5^2, which equals 25 iterations or 25 elements paired together. You can see how increasing the size of the array can drastically increase the processing time for looping through the data.
Naturally, the more nested for-loops that exist, the higher magnitude the time complexity becomes.
As you can imagine, the deeper you go in nested looping, the more complex an algorithm runtime becomes. Consider the example below.
In the above code, we’ve gone one level deeper in complexity. The complexity for this code is considered O(n^3).
The more nested for-loops that an algorithm contains, the longer the runtime becomes, thus the longer it takes to complete a run of the software. You can see how runtime complexity can become particularly important when designing complex algorithms for software.
There are a large variety of algorithms and data structures that are used specifically for handling certain runtime complexity issues. It’s a good idea to learn about the various options available to you when designing solutions.
Now that we’ve described the basics behind algorithm complexity analysis, let’s take a look at some of the more popular algorithms that keep runtime complexity in mind. In particular, let’s look at the more popular sorting techniques of Quicksort, Mergesort, Insertion Sort, and Selection Sort.
We’ll start with Quicksort, which is one of the most popular sorting techniques used by developers. It’s not only one of the more optimal methods for sorting data, running (on average) in O(n * log(n)) runtime, but it’s also used in many software development libraries as the default sorting technique (for example, .NET and Java both use Quicksort). This is because Quicksort has an added advantage of being efficiently implemented on many architectures. (As an aside, .NET actually uses a customized form of Introspective sort, combining Quicksort, Heapsort, and Insertion sort depending on the data size. See the MSDN page on Array.Sort for details.)
While quicksort might sound complicated, it’s actually pretty easy to implement. The algorithm works through a divide and conquer approach. An array to be sorted is broken in half, and each half is then sorted. Here is a description of the algorithm:
- Select a random value from the array (such as the first one).
- Put all values less than the value in an array named “left”.
- Put all values greater than the value in an array named “right”.
- If array “left” or array “right” has more than one value, repeat the above steps on it.
- The sorted result is array “left” + selected value + array “right”.
Let’s see how to implement this in a code example.
The above code uses recursion to repeatedly sort the left and right halves, until they contain just a single element to be combined together. This is how the divide and conquer approach works to help optimize the solution.
The above implementation is a basic example of quicksort and you can find many different implementations online. Let’s take a look at the next sorting technique, mergesort.
Mergesort is another popular sorting technique that is used in many software applications and frameworks. Java actually uses mergesort, along with quicksort, when sorting arrays of data (depending on the type). This is due to mergesort being more effective on certain types of data. Both quicksort and mergesort run in an average case of O(n * log(n)) runtime complexity.
Similar to quicksort, the mergesort algorithm is also straight-forward to understand and implement, operating on a divide and conquer approach. The algorithm is, as follows:
- Separate each item to be sorted into its own group of 1 (one element is effectively sorted, by default). Do this by repeatedly dividing the array in half until each half contains just 1 element each.
- Combine adjacent groups by pushing each element onto its own stack (stack 1 and stack 2). The stack will be in sorted order, with the smallest at the top.
- Take the smallest value from either the top of stack 1 or stack 2 and add to the front of a new group. If no more elements exist in a stack, take the remaining stack and add to the new group.
- Repeat until no more values exist in the stacks.
- If more than 1 group remains, repeat steps 2-5.
Let’s take a look at a code example to implement mergesort.
As you can see in the above code, we first calculate the midpoint of the array. We then split the array into a left and right portion. Next, we use recursion to split the left and right sides again, repeating until only a single element remains in each side.
Once we’ve narrowed the splits down to single elements, we begin the merging process. We step through each half and take the smallest value from the front of each array (i.e., the top of the stack) and add them to a merged result. If we run out of values in either list, we just append the remaining list to our result. This effectively combines the two sides together in sorted order, which gets returned back to the recursive process, merging with the other halves, until all halves have been merged together.
Now that we’ve covered two O(n * log(n)) sorting algorithms, let’s take a look at two simpler, but typically less efficient sorting algorithms. We’ll start with insertion sort.
The insertion sort algorithm takes a simplified approach to sorting a list of numbers. The method compares the first value in a list with each subsequent value, until one that is less is found. It then shifts all of the other values up a position, making room to insert the smallest value into position. The steps are highlighted below.
- Starting with the first value in the list, compare the next value with the prior.
- If the prior value is larger, shift it up a position.
- Repeat shifting all values to the left of the smaller element up a position until the value is no longer smaller.
- Insert the smaller element into the newly made position.
While insertion sort is simple to implement and efficient for small, mostly sorted, data sets, the core problem with this method is its overall runtime inefficiency. By design, it uses a nested while loop to iterate over the elements at each iteration of the array to be sorted. It does this in order to locate the correct position to insert the smaller value. In doing so, insertion sort is a time complexity of O(n^2).
A code example for insertion sort is shown below.
Notice in the above code how there is a nested while loop within the for loop. It’s this double looping that causes insertion sort to be O(n^2) in runtime complexity.
Let’s review one final sorting method that is similarly simple to insertion sort, but suffers from the same efficiency problem of having an O(n^2) runtime complexity.
Selection sort follows another simple sorting pattern, as shown below.
- Starting with the first value in the list, find the smallest element.
- If the smallest element is not the current position, swap it with the value at the current position.
- Move to the next value in the list and repeat steps 1-3, until you reach the end of the list.
Below is a code example for implementing selection sort.
Notice in the above code, similar to selection sort, insertion sort has a nested loop to iterate over each element of the array. It does this in order to locate the smallest element at each step and then swap its position with the current index. It’s due to this nested looping that selection sort has a runtime complexity of O(n^2).
Now that we’ve covered sorting and dug a little deeper into runtime complexity analysis, the next topic to consider is how to speed up an algorithm. One of the more common methods for increasing runtime speed is through the use of hashtables.
The hash table is a data structure that has an O(1) runtime complexity, which is quite fast, taking just a single instruction to access a key/value pair. It can greatly speed up the runtime of an algorithm by effectively caching values that can be quickly looked-up in subsequent calls, as needed.
While hash tables are very fast and convenient for accessing cached values, they do take up additional storage. This can be in the form of memory or disk persistence. Therefore, the increase in runtime speed comes at the cost of space. However, in many cases, this is an acceptable tradeoff, especially as the costs for storage go down.
A hash table can be implemented either via an array or by using an associative array. Here are two examples of caching with a hash table.
In the above example, we’re simply using an array to store the value “1” at index 0. Assuming that “0” is a valid key for our data, we can quickly access its associated value by simply reading that index from the array.
Likewise, we can do the same with an associative array (i.e., a hashtable), as shown below.
In the above example, we’ve created an associative array with two keys in it. We can access the key/value pair for any entry by using the key as the index. In this manner, you can cache and retrieve data for an associated key/value pair that your algorithm requires.
Let’s take a look at how we can utilize hash tables to speed up an algorithm’s runtime.
Consider the problem of counting the number of times each letter occurs within a string. For example, in the string “mississippi”, we want to count the number of times each letter appears in the string. In this case, “m” would equal 1, “i” would equal 4, “s” would equal 4, and “p” would equal 2. The total count of letters is thus 11 characters, with 4 unique characters.
A naive approach to counting the letter occurrences in a string would be to simply loop over the string for each letter and count the number of times it appears. An example is shown below.
In this example, we’ll simply loop over the string for each character and count the number of times they appear. The code example for this is shown below.
You can see in the above code how we loop across the string and count the number of times our target letter appears. Since we have a single for-loop, this algorithm has a runtime complexity of O(n). That is perfectly fine, however, if this method needs to be called many times, it might be wasteful to continuously loop across the string recounting the number of times a letter appears, especially when we’ve already calculated the sum. This is where caching with a hash-table can speed things up.
Let’s build a hashtable that contains the number of times each letter in the string appears. We can then use the hash to instantly find the counts for any desired letter.
In the above code for
letterCounts we loop over the string and calculate the number of times each letter appears, incrementing the value for each letter key in our hashtable. While we have the same for-loop and runtime complexity of O(n), as the prior example, this particular method only needs to be executed a single time. Once we have the hash, there is no need to run this method a second time. We can simply access the hash, directly, to obtain letter counts. This is shown in the second example above, where we retrieve the letter counts for each letter in the word, using a runtime complexity of O(1).
As you can see, if we need to repeatedly retrieve letter counts in a string, the hashtable solution is far quicker and more optimal for returning results.
The next important topic to review is how to form combinations and permutations from an array of data. This can be a relatively common task, especially when comparing and contrasting elements within a list to search for specific features.
First, let’s briefly define the difference between a combination and a permutation.
A combination is a selection of unique items from a list, without considering the order that the items are selected. That is, duplicate items are not permitted in the list (i.e., [A, B] and [B, A] are not part of a combination).
For example, if you have a list of items [A, B, C, D, E], the combinations from this list will include [AB], [AC], [AD], [AE], [BC], [BD], [BE], [CD], [CE], [DE].
To calculate the number of combinations that can be formed from selecting r elements from a list of n total elements, we can use the “n choose k” formula, as follows:
n is the number of total elements in the list.
k is the number of elements within each pair.
n! / k!(n- k)!
Let’s take a look at some quick examples. The number of combinations that can be formed from the first example above (letters A-E) by selecting any two letters, turned out to be 10 different combinations. This can be calculated as follows:
5C2 = 5! / 2! (5 - 2)!
5C2 = 120 / 2 (3!)
5C2 = 120 / 2 6
5C2 = 120 / 12
5C2 = 10
[A, B, C, D, E]
[AB], [AC], [AD], [AE], [BC], [BD], [BE], [CD], [CE], [DE]
What if we wanted to select 4 elements from the list and form combinations? That would be 5 choose 4, or 5C4.
5C4 = 5! / 4! (5 - 4)!
5C4 = 120 / 24 (1!)
5C4 = 120 / 24 1
5C4 = 120 / 24
5C4 = 5
[A, B, C, D, E]
[ABCD], [ABCE], [ABDE], [ACDE], [BCDE]
To calculate the number of combinations or permutations that can be created in a given set, we’ll need to use the factorial function, as described in the above formulas.
We can easily write a factorial function with the following code.
With the factorial function created, we can now calculate the number of combinations by using the following code example.
A permutation is a selection of items from a list where the order does not matter. This means, the selected pairs can include duplicate items in differing orders (i.e., [AB] and [BA]). (In fact, combination locks for doors, lockers, and bike chains might be better named “permutation locks”, since they allow for differing orders of the same digits in a password!)
For example, if you have a list of items [A, B, C, D, E], the permutations from this list will include [AB], [BA], [AC], [CA], [AD], [DA], [AE], [EA], [BC], [CB], [BD], [DB], [BE], [EB], [CD], [DC], [CE], [EC], [DE], [ED].
To calculate the number of permutations that can be formed from selecting r elements from a list of n total elements, we can use the following formula, as follows:
n is the number of total elements in the list.
k is the number of elements within each pair.
n! / (n- k)!
Just as we did for combinations, let’s take a look at some quick examples. The number of permutations that can be formed from the first example above (letters A-E) by selecting any two letters, turned out to be 20 different permutations. This is larger than the number of combinations because permutations allows items to be re-selected, but in a different order. This can be calculated as follows:
5P2 = 5! / (5 - 2)!
5P2 = 120 / 3!
5P2 = 120 / 6
5P2 = 20
[A, B, C, D, E]
[AB], [BA], [AC], [CA], [AD], [DA], [AE], [EA], [BC], [CB], [BD], [DB], [BE], [EB], [CD], [DC], [CE], [EC], [DE], [ED]
What if we wanted to select 3 elements from the list and form permutations? That would be 5 permute 3, or 5P3.
5P3 = 5! / (5 - 3)!
5P3 = 120 / 2!
5P3 = 120 / 2
5P3 = 60
[A, B, C, D, E]
[ABC], [ABD], [ABE], [ACB], [ACD], [ACE], [ADB], [ADC], [ADE], [AEB], …
Just as we did with the combination counts, we can calculate the number of permutations by using the factorial function, as well. The code example for this is shown below.
Now that we’ve described the difference between combinations and permutations and have created functions for calculating the number that can be generated, let’s see how to actually generate the sets with code.
Since we’re comparing each element against the others, generating combinations requires a nested loop as we iterate over the elements within the list. Due to the nested loop, generating combinations has a runtime complexity of O(n^2). A code example for generating pairs of 2 combinations is shown below.
Notice in the above code for generating combinations, our inner for-loop begins at one step past the outer loop’s starting position. In this manner, combinations will select unique element pairs.
Just as we did with the generation of combinations, we can generate the set of permutations by using very similar code. The difference is that instead of starting the inner for-loop at one step past the outer loop’s starting position, we’ll simply start at position 0, allowing elements to be reused in different orders. A code example is shown below.
The above two code examples are used for generating pairs of combinations and permutations from a set. That is, each combination or permutation consists of 2 selected elements from the list. If we want to select 3, 4, 5, or K elements for each combination or permutation, a different algorithm is required.
For the case of using a variable length set size, the code will be required to keep track of the last index used, as well as the current index across the set. You can refer to the code examples to find example functions for doing this.
Below is an example of the code running.
Now that we’ve seen how to generate combinations and permutations, let’s see how it can be applied.
Suppose we want to find all pairs within a set that generate a certain product. For example, if we have a list of numbers [1, 2, 3, 4, 5] and we want to find all pairs of numbers that can be used to create the product 12, the answer would be [3, 4].
We can solve this problem by generating all possible combinations from the set and calculating their products. We wouldn’t use permutations, because 3 × 4 == 4 × 3, which both equal 12. In this case, combinations are what we’re after.
When working with arrays and lists of data, code often has to loop over the data and perform some kind of calculation. The two styles for looping over the data include iterative and recursive approaches.
When using an iterative approach, a while or for-loop is often used to iterate from the first position in the array to the last. By contrast, when using a recursive approach, the function calls itself repeatedly until all of the data within the array has been consumed.
Recursive functions require a base-case. This consists of a test to determine whether further code within the function should run, which will result in recursively calling the same function again. When the base-case is valid, the recursion stops, allowing the result from the calculations to bubble back up the stack to the original caller. It’s a bit easier to see an example!
During our prior topic of combinatorics, you may recall that we used a factorial function for calculating the number of combinations or permutations that can be generated from a set. It just so happens that the factorial function can provide a perfect example of the difference between iterative and recursive functions.
The iterative factorial function is shown below.
Notice, the iterative factorial function includes a for-loop that iterates from the starting number until it reaches 0. At each step, we multiply the result by the current number.
Let’s take a look at what a recursive factorial function looks like.
In the above recursive implementation, we’ve defined a base-case at the top of the function. The base-case checks if n is either 0 or 1. If so, we know the answer to factorial(0) and factorial(1) are both 1. Therefore, there is no need to recurse any further, and we can simply return 1. For all other values of n, we set the result to be n multiplied by the value returned from the same factorial function using the parameter n - 1 (the number that comes before it). In this manner, we recursively call the factorial function for each digit down the line, until we reach the base-case of n equaling 1.
Running the code with some logging statements, shows the following result:
You can see how the recursive property of the function calls itself until the final answer is obtained. You can play with both the iterative and recursive code examples to see how they work.
Let’s take a look at one more example of iterative versus recursive functions. This time, we’ll look at the code for generating the fibonacci sequence. The Fibonacci sequence contains a series of values, where each value is the sum of its two prior values. Starting from 0, 1, the next value is 1 + 0 = 1, giving us 0, 1, 1. The next value is 1 + 1 = 2, giving us 0, 1, 1, 2. The next set of steps gives us 2 + 1 = 3 and 3 + 2 = 5, giving us 0, 1, 1, 2, 3, 5, 8, 13, 21.
We’ll start with an iterative approach, as shown below.
In the above iterative approach, we use a for-loop to iterate from 0 until we reach n, appending the resulting values of the fibonacci sequence to the result array. Just as we saw with the factorial function, we can apply a recursive approach to get the same result.
Let’s rewrite the fibonacci function using a recursive approach. Instead of using a for-loop to iterate over the sequence, we’ll recursively call the function itself, to generate the resulting values. The code example for this is shown below.
Notice how the above recursive code includes a base-case. Just as we saw with the recursive factorial function, the recursive fibonacci function uses a base-case to determine if the current sequence value is 0, 1, or 2. If so, we immediately know the result and can return the answer. For all other values, we recursively call the function again, summing the two prior resulting values from the function until the final result is obtained.
Since we’re generating a sequence, we have also created a helper method,
fibSequence, which builds the complete sequence from the recursive code.
Another topic in algorithms is the method for using binary search to find a target within an array. Binary search uses a divide and conquer approach for quickly honing in on the target value within a sorted list of items.
Binary search can be more easily explained by thinking about the classic number guessing game. One person thinks of a number from 1-100. The second person has to guess the number. At each guess, the first person says whether the guess is too high or too low. Now, the second person could randomly make guesses until they eventually arrive at the answer. However, a smarter approach is to utilize the clue of higher or lower to narrow down on the answer. Specifically, the guesser can divide in half at each guess, until they narrow down on the result.
For example, Player 1 chooses the number 76.
Player 2 divides the range 1-100 in half and guesses 50.
Player says “too low”.
Player 2 now knows the answer can’t be 50 or less.
Player 2 divides the range 51-100 in half and guesses 75.
Player 1 says “too low”.
Player 2 now knows the answer can’t be 75 or less.
Player 2 divides the range 76-100 in half and guesses 88.
Player 1 says “too high”.
Player 2 now knows the answer can’t be 75 or less or 88 or higher.
Player 2 divides the range 76-87 in half and guesses 81.
Player 1 says “too high”.
Player 2 now knows the answer can’t be 75 or less or 81 or higher.
Player 2 divides the range 76-81 in half and guesses 78.
Player 1 says “too high”.
Player 2 now knows the answer can’t be 75 or less or 78 or higher.
Player 2 divides the range 76-78 in half and guesses 77.
Player 1 says “too high”.
Player 2 now knows the answer can’t be 75 or less or 77 or higher.
Player 2 divides the range 76-77 in half and guesses 76.
Player 1 says “you win!”
Binary search can be applied just like the number guessing game to efficiently find a target value within a sorted list. In fact, it can be used not just for single one-dimensional arrays, but for two or more dimensional matrices as well!
Let’s take a look at an example of searching for a value within a sorted array. A code example is shown below.
You can see, in the above code example, how the function uses binary search to find the target value in the sorted array. It does this by dividing in half the search space at each iteration, until the minimum window is greater than the maximum window, at which point we’ve found our target. In the case that the target doesn’t exist, our
min counter will be greater than our
max counter, and we can return -1.
You can imagine how this can drastically cut down on the time it takes to search within an array, especially if the array is very large. For example, consider a larger array and target, as shown below.
Linked lists are a type of data structure that consists of individual nodes connected by pointers to their child and/or parent nodes. Each node in a linked list points to the next node. In this manner, linked lists can be traversed.
Linked lists can be traversed using a variety of algorithms, depending on the type of structure. For single node linked lists, where each connects just 1 other child node at a time, you can use iterative or recursive traversal.
For linked lists where each node can contain one or more child nodes, also called trees, some of the more popular traversal algorithms include depth first search (DFS), breadth first search (BFS), and the A* algorithm. DFS and BFS both have runtime complexities of O(|V| + |E|), which can be quite CPU intensive. By contrast, the A* algorithm uses an intelligent heuristic to traverse, and can be much more efficient at searching a linked list.
Let’s take look at how to construct a linked list.
The above data structure is sufficient to create an entire linked list. After all, we only require a means of connecting nodes to each other, which is done via the
next property of the node.
Below is a method for creating a simple linked list.
As you can see in the above example, we’ve linked together five nodes, containing the values of the digits 1-5. Let’s write a small function to traverse the linked list and return the values in each node.
We can traverse a linked list using the following code example below.
In the above code, we’re simply following each node’s
next property to access the next node. At each step, we can the
callback function, passing in the node for processing by the caller.
Since linked lists are connected by a pointer to their child node, there is no direct reference from the child node back to the parent. However, we can still reverse linked list, as shown below.
In the above code, we’re reversing the linked list by setting each node’s
next property to point to their parent’s node. We obtain the parent node through the recursive process by accessing each child and then passing the child, along with the original node, back into the recursive process. In this manner, each node will point to its parent. Finally, we return the last child node, as the new root.
The code to reverse a linked list can be created by using an iterative or recursive fashion.
We can remove nodes from a linked list by following a similar pattern as the above techniques for traversing and reversing a list.
To remove a node, we begin at the head and traverse down the linked list until we reach the desired position. Once there, we set the value for
next to be the subsequent child’s
next. This effectively removes the target node from the chain, since the parent of the target now skips the target node and points directly to the target’s child. The code is shown below.
So far, we’ve seen a linked list where each node connects to a single child node. When you change the
next property to allow an array of child nodes, you’re effectively creating a tree.
A tree is a linked list where each node can contain one or more children. Trees can be traversed with depth first search, breadth first search, and a variety of other traversal algorithms.
Let’s begin by creating a tree.
Below is an example of constructing a tree with a linked list.
In the above code, we’re simply creating a new node. The difference between this example and the prior linked list example, however, is that we’re using an array to represent the child nodes. When inserting a new value into the tree, we push a new node onto the parent’s children array. This effectively links multiple nodes to the parent.
Below is an example of creating a tree that contains colors.
The above tree can be visually represented as shown below.
Since a tree contains multiple children at each node, we’ll need to use a traversal algorithm to walk across each node and work its way down the depth of the branches. Let’s see how this is done using depth first search and breadth first search.
Below is an example of using depth first search to traverse a tree.
In the above code, we’re using a recursive process to walk down each path of the tree. We begin at the root and recursively traverse each child node, deeper and deeper, until no more children are found for the given path. We then back-up in the recursive process and begin heading down the next child node path. We repeat this process until all paths within the tree have been explored.
Notice in the output of the
traverseDFS function, we can see the display of each visited node along each path. The first line is the root
red node. The second line is the first leftmost child of the root, also called
red. That node’s children are then accessed, outputting
brown in order of each node being visited. This exhausts the leftmost branch.
The next branch that is visited is the
green node, followed by its children,
violet. Finally, the process is repeated for the
blue branch as well.
Depth-first search can be implemented with a stack data structure. In this manner, the stack stores each discovered child at the top and will return, or “pop”, it first when requesting the next node to traverse. This takes us deeper within the tree at each iteration. Stacks work on a first-in-last-out approach (FILO) which lends itself to depth-first search for exploring discovered nodes.
By contrast, breadth-first search can be implemented with a queue. In this manner, child nodes are appended to the end of the list, but the next node to be explored will be the first, or oldest, one that we’ve come across so far (the top-level child). Queues work on a first-in-first-out approach (FIFO).
Similarly to depth first search, we can apply a breadth first search algorithm to the tree. This allows us to traverse each layer in full, before going deeper into the tree.
An example of breadth first traversal is shown below.
In the above code, notice that we’re no longer using recursion for this process. Instead, we’re using a while loop that processes a fringe array. The
fringe consists of all visible nodes that have been discovered at the current depth. Each time we discover a new node, we add it to the fringe, to eventually be processed by the callback. Once we finish processing the current node, we pop the next node off of the fringe and repeat the process until all depth layers and nodes have been processed.
You can see in the traversal output how there is a difference in the nodes that are discovered. In this example, we first process the
red root node, followed by its children,
blue. This is immediately different than depth first search. Instead of walking down the
red branch towards its child leaves, we instead process all child nodes at the current depth (1). Next, we move on to the next depth layer, which discovers the bottom leaf nodes,
Both algorithms discover all 13 nodes. However, they differ in the order of discoverability. Depth-first search is usually used to find complete paths down a tree, from root to leaf. Breadth-first search is used to discover the tree one layer at a time. This opens up the potential to apply a heuristic approach to traversing the tree, effectively changing the way traversal occurs, depending on the values found at the current level.
This leads us to the A* algorithm.
The A* algorithm uses an intelligent heuristic for traversing a tree. At each level, and each step in the traversal process, the A* algorithm calculates a score for how close it is to a particular goal. In this manner, A* can guide traversal down specific paths or branches, aiding it in efficiently finding an optimal solution.
A* works by first collecting all visible nodes at the current depth in the tree. A heuristic function is applied to each node, calculating the cost (h), along with an additional cost for distance (g). In the case of tree traversal, the distance cost can simply be considered the depth. The total cost for a node is h + g. When the cost for a node reaches 0, it can be assumed that a solution is found. Once a solution node is reached, you can traverse backwards up the tree, from solution node to root, recording each visited node as the solution path.
Let’s modify our tree from the previous example to make it slightly more complex. This will give the A* algorithm a little more to work with. We’ll use the following tree shown below.
We’ve expanded our example tree to include an additional layer deeper. This tree is constructed with the following sequence of commands.
Let’s suppose that we want to find the node
lime. How can we do this? We’ve learned previously that we could traverse the tree using breadth-first or depth-first search, in order to locate the node. Let’s see how many steps it takes to find this node.
Breadth-first search traverses the tree by exploring each child node at the current depth, before moving a layer deeper, until the goal
lime node is found. It visits the following list of nodes, shown below, before discovering the solution.
Breadth-first search visited 18 nodes before arriving at the solution. In fact, that consists of all nodes in the tree! That is certainly the worst-case scenario, with regard to runtime complexity and CPU processing time. BFS did this because it explores all child nodes at the current depth, before moving deeper and repeating the process. Since our goal node is located at the very bottom layer, and at the far-right of the tree, it will be the last node discovered.
Let’s see if depth-first search can do any better. Recall, DFS traverses from root to leaf, cutting through each layer in the tree to the very bottom, as it moves across the branches. In this manner, we should expect the goal node to be discovered in less steps than breadth-first search. This is because the goal node is not at the end of the tree, when DFS is concerned. The node
black is located at the far-right, which will not be visited in DFS, as our goal node
lime should be reached beforehand.
Let’s run the algorithm and see how it does.
As we can see in the above results, depth-first search was indeed faster, in that it discovered the goal
lime node before exhausting every single node in the tree. It was able to skip the
black node, since it already discovered the solution.
Both breadth-first search and depth-first search are capable of finding a solution path to a goal node. However, they work by brute-force in their searching process.
Let’s take a look at how the A* algorithm uses an intelligent heuristic to efficiently find a solution path in far fewer steps.
We can implement the A* algorithm in a similar manner to breadth-first search, but instead of a callback parameter, we’ll provide a cost function. The cost function, created by the calling client, will return a cost for the current node. A* will call the cost function each time it discovers a new node, so that it can prioritize which nodes to visit next.
Below is an implementation of the A* algorithm for traversing a tree.
The first item to note is that we have an array called
fringe. This array contains the currently discovered nodes that are still to be explored. When we start the algorithm, we initially populate the fringe with our root node. We also apply the cost function to the root node and assign a depth cost of 0. We then begin looping for as long as we have more nodes to explore and we have not yet arrived at the solution node.
At each iteration, we check if the cost for the current node is 0. If it is, then we know that we’ve arrived at a solution node. In this case, we walk backwards up the tree, saving each parent node in our solution array to be returned as the result.
If a solution is not yet found, we find all child nodes at the current level and add them to the fringe array. We apply the cost function to each node, along with a value for depth + 1 (since the child node is located 1-level deeper than the parent).
Finally, we sort the fringe in descending order of cost. In this manner, the least cost nodes are located at the end of the array, while the most expensive are located at the front. When our while loop iterates, it will pop the lowest costing node from the fringe to be explored next. This is how A* is able to efficiently explore the tree, without examining every single node across the branches.
Let’s see how it runs.
To use A*, we’ll call the
traverseA function and pass it a cost function for determining the cost of a given node. In particular, we’re looking for the
lime node. We’ll use a landmark-based heuristic to guide the A* algorithm. In this manner, we’ll decrease the cost of a node if we know it’s on the way to the goal.
There are many different types of heuristics that can be applied to nodes with the A* algorithm, but we’re using a landmark-based one for simplicity.
The code example below shows how the A* algorithm is called on or tree, along with the cost function.
While running the above code, we can see the following list of nodes as explored while traversing with the A* algorithm.
Notice how the A* algorithm traversed immediately down the correct branch,
gray, and finally arriving at
lime. It did this because the cost of these nodes decreased, while the other costs remained higher.
We can print the solution path, as recorded by A* in the solution, using the following code.
A* took just 4 steps to discover the solution!
A binary tree is a type of tree that consists of a left and right child at each node. In our prior tree example, we were using a tree where each node could connect to one or more child nodes. By contrast, a binary tree only contains, at most, two child nodes for any node. In addition, the child nodes are ordered based upon their value. The left child node is less than the parent node, while the right child node is greater than the parent node. In this manner, a binary tree offers a way of tracking values, and even sorting data, in a particular order.
When inserting a new node in a binary tree, you first traverse the tree in order to find the correct location to insert the new node. Starting at the root, if the new value to insert is less than the root, we move left. If the new value is greater, we move to the right. We repeat this process, traversing down the tree, until we reach an empty slot to insert our value, so that the parent node is greater than the new value (if inserting as a left child) or less than the new value (if inserting as a right child).
Let’s construct a binary tree. We can start by implementing the
insert method, just as we did with our other trees. The difference, this time, is that we’ll locate the child node to insert the new node under.
The following code example constructs a binary tree.
Notice in the above code, we first check if a root is available. If it’s not, then this is the first node that we’re creating. Otherwise, we start traversing the binary tree, left and right, according to whether the new value to be inserted is less than or greater than the current node. When we find an empty slot, we insert the new value on the proper leaf.
Let’s create a small binary tree.
The above code creates a binary tree that appears, as follows.
Since a binary tree is constructed using a set of rules for where to insert new values, we can search a binary tree in an efficient manner to locate a target node.
The code example below implements a function to check if a value exists in a binary tree.
The above code is very similar to the logic used in the
insert function. We simply traverse left or right, depending on whether the value being searched is less than or greater than the current node. If the value is equal, then we’ve found the node and return true. If no more child nodes exist on the path, we return false.
The different methods for traversing correspond to how each node in the binary tree is visited, and thus, the order of the values that are returned. For example, inorder traversal will return a sorted list of values from the tree. All three traversal types follow a very similar code style, differing only in the step where the node’s value is returned.
Let’s take a look at the code to walk through a binary tree using each of the three methods. We’ll start with preorder traversal.
If you recall from earlier, we constructed a very simple binary tree consisting of 5 nodes, as shown below.
When using preorder traversal, we’ll walk through the nodes starting at the root 10. Next, we’ll always head left towards the smaller values, and record the value at each node. In this manner, we find 5, and then 3. Since we’re at a terminal leaf, we’ll move back up and to the right, finding the node 6. We repeat the process, moving back up and to the right, to find the node 20.
The preorder traversal algorithm is shown below.
- Check if the current node is null.
- Display the value of the current node..
- Traverse the left subtree by recursively calling the pre-order function.
- Traverse the right subtree by recursively calling the pre-order function.
Below is a code example for traversing a binary tree, using preorder traversal.
In the above code, notice how we simply print the current node’s value, followed by traversing the left, and then the right, branches. This is how we give preference to the smaller values in the tree, moving left, until we hit a terminal leaf, and then moving back and to the right.
Similar to preorder traversal of a binary tree, postorder traversal is essentially the preorder algorithm, but reversed. In postorder traversal, we hold off from returning the value of the current node, and instead traverse first. We still traverse towards the left, locating the smallest values first, followed by backing up and moving to the right. However, the main difference from preorder traversal is in the order that we return the node values.
The postorder traversal algorithm is shown below.
- Check if the current node is null.
- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Display the value of the current node..
The code example below shows a postorder traversal of a binary tree.
The final traversal type that we’re cover is inorder traversal of a binary tree. This allows retrieving the values in a binary tree in sorted order, from smallest to largest node values.
The inorder traversal algorithm is shown below.
- Check if the current node is null.
- Traverse the left subtree by recursively calling the in-order function.
- Display the value of the current node..
- Traverse the right subtree by recursively calling the in-order function.
The code example below shows an inorder traversal of a binary tree.
So far, we’ve shown code examples for recursively traversing binary trees. This is the simplest way to traverse this type of tree. However, it can also be done iteratively. To traverse iteratively, we’ll be required to keep track of visited nodes that we’re not yet displaying the values for. We can use a stack for this purpose, popping the next node off of the stack when we reach a leftmost leaf. In this manner, we can traverse, save off nodes, and display node values in the designated pre/post/in order traversal.
The code example below shows inorder traversal of a binary tree, using an iterative style.
Now that we’ve seen how to construct and navigate a binary tree, let’s combine this knowledge with what we’ve learned from searching. Suppose you want to determine the maximum depth of a binary tree. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
We can find the maximum depth of a binary tree by using either breadth-first search or depth-first search. Both algorithms will explore the tree from root to leaf and allow us to find the lowest leaf node.
Let’s use the same binary tree from our example before, with one addition child node (1). As you recall, we can construct the tree with the following commands.
The above code creates a binary tree that appears, as follows.
The maximum depth for our tree is 4, with the leaf node
1 at the deepest level.
We can implement depth-first search to find the maximum depth of this binary tree. Our search will start at the root and traverse down each branch, until it reaches a leaf node with no children (i.e., no left or right child node). We’ll then compare the depth that we’ve reached against the maximum depth so far. If the new maximum depth is greater, we’ll update our result.
The following code determines the maximum depth of a binary tree.
As you can see, we start at the root with a depth of 1. We actually add the root node onto our fringe of nodes to be explored, assigning it an initial depth of 1. We then begin the process of locating all child nodes (left and right). Each child node is pushed onto the fringe. Recall, that a stack is used for depth-first search and a queue is used for breadth-first search.
Next, we check the current depth and pop the next child node off of the stack. We’ll continue drilling down the right-most branch until we reach a leaf with no child nodes. At this point, the next node to be popped off the stack will be the most recent right-most branch that we’ve discovered. We repeat this process until no more nodes are left to be explored. Our final result is the maximum depth of the binary tree.
Before we finish up talking about binary trees, there is a specialized type of binary tree called a “heap”.
Binary heaps look and behave just like the traditional binary tree, as discussed above, with an additional set of constraints on how items are added to the tree. Specifically, a binary heap adds items to the binary tree such that every child value is less than or greater than the parent value. Heaps are useful for situations where you frequently need to locate the smallest or largest value within a collection.
For min-heaps, every child value on the binary tree is greater than the parent value. The root holds the minimum value of the tree.
For max-heaps, every child value on the binary tree is less than the parent value. The root holds the maximum value of the tree.
Additionally, binary heaps are complete binary trees. That is, all levels of the tree are fully filled, except possibly for the last level. When adding new values to a heap, the leaves are fully filled from left to right.
With standard binary trees, as discussed earlier, we add new values to the tree by traversing left or right depending on the new value being greater or less than the parent. With binary heaps, we always move from left to right, locating an empty leaf on the tree to insert the value at the correct level.
Binary heaps allow searching in O(n) time complexity, inserting on O(1) and peeking (i.e., obtaining the minimum or maximum value at the root of the heap) in O(1) time complexity. In this manner, they can be an efficient way of working with sorted data.
To insert a new value into a binary heap, we can follow the steps listed below.
- Add the element to the bottom level of the heap.
- Compare the added element with its parent; if they are in the correct order, stop.
- If not, swap the element with its parent and return to the previous step.
By repeating these series of steps, the value added at the bottom of the heap, can “bubble-up” to the correct level, thus maintaining the order of the heap.
Similarly, to remove a value from a binary heap, we can follow the steps listed below.
- Replace the root of the heap with the last element on the last level.
- Compare the new root with its children; if they are in the correct order, stop.
- If not, swap the element with one of its children and return to the previous step. That is, swap with its smaller child in a min-heap and its larger child in a max-heap.
This series of steps can be thought of as “sinking down” the value towards the correct level of the heap.
An example of implementing a min-heap can be found at the link provided. We can utilize the min-heap to store and retrieve sorted values as shown below.
Notice in the above output, how we’re able to access the randomly added values in sorted order, starting from the minimum value. The number
2 is present in the output (even though we’ve called
heap.remove(2)), as it was added to the heap twice.
Let’s begin by creating a simple class to represent a person object. We can use the
class declaration to create the object. We’ll construct our person object to support a first and last name, as shown below.
The above object-oriented class defines a
Person object. Notice that our class contains a constructor to initialize the first and last name properties. We’ve also included a class method,
toString(), which simply returns the person in a string format.
We can instantiate a new person object by using the
new keyword, as shown below.
We can define a function outside the scope of the Person object to generate ids for us. An example is shown below.
The above code will initialize an id value within the
generateId function of
1. Each time the function is called, the value will be incremented accordingly. In this manner, we can utilize this method within our person class to generate id values, as shown below.
We can use the above class to output the person, including their auto-generated id value, as shown below.
Notice how our global
generateId function is able to automatically increment the id value for each instantiated
With the above extension, we can now instantiate both generic
Person objects and specific
Employee objects, as well. An example of this is shown below.
Now, if we run the above code, we’ll still see the same output for the first and last name, along with the auto-generate id, but we’ll also have access to the new Employee method
isManager, which will display
A closure is essentially a way to encapsulate a variable within a child scope. That is, if a particular function declares a local variable, normally when that function terminates, the variable is no longer in scope. This is the typically expected behavior of programming environments. With the exception of global or class-level variables, local variables are not retained when a function or method exits.
A closure allows you to encapsulate a local variable and thus, retain access to the variable’s value from within the scope of a child function. In this manner, child scopes can utilize variables that were declared in the parent scope, as long as they’ve created a closure around the variable.
function keyword from within another function, you are creating a closure. In this context, accessing any variable outside of your immediate lexical scope creates a closure.
Let’s take a look at a simple example.
We’ll create a simple function to say hello. The function will contain a local variable, containing the text message that is to be printed. We can create the function as shown below.
In the above code, we’ve defined a simple function
sayHello. The function takes a name as an argument and contains a local variable for displaying the message. In a traditional scenario, when the function exits, the local variable
text would be lost. If that were to happen, the child
say function would lose the value of text and be unable to print it. However, the child function is creating a closure around
As you can see in the output shown above, after the
sayHello method exits, we can still call
say() and the correct text message is printed. This is because the variable
text has been wrapped within a closure, created by the child function.
In fact, if you peek at the output of
say.toString(), you can actually see how the code refers to the variable text.
Additionally, you can call the
sayHello function as many times as you like. Each child function returned will still retain the correct message to print, since each function maintains its own closure of the variable
An interesting scenario, which is often asked during interviews as a trick question, occurs when you attempt to utilize a for-loop variable from an event callback handler, such as jQuery or native DOM event handlers.
Consider the following simple code example, which contains several buttons with assigned click event handlers.
Upon initial glance, the above code looks like it should simply print 0, 1, 2 when each of the three buttons are clicked. After all, the for-loop iterates across each button, assigns a click-event handler, and prints the value of
i when the button is clicked.
If you run the above code, you’ll see the output is actually the final value of
i for each button click.
What’s actually happening here is that the for-loop value for
i is changing its value, leaving the final value as the result to the click event handler.
To correct this situation, we can utilize a closure, passing in the specifically desired value of
i so that the click event handler has an instance of the actual desired value. This is shown below.
In the above code, we’ve slightly changed our click event handler to include a closure function around the outside of it. This particular closure accepts a single parameter for the value of
i and then passes that value to the scope of the child function. This gives the click event handler access to the locally passed-in variable, and thus, it can now print the correct value.
Also notice how the click event handler refers to the variable
x, which is defined within our closure, and not the variable
i. We assign the variable x to hold the value of i and then pass it to the enclosed child scope.
In addition to reviewing the overall topics of data structures and algorithms, you may also want to practice your skills on a variety of problems. There are several sites available where you can train and hone your skills, in preparation for a technical interview or whiteboard session. Sites such as HackerRank and LeetCode offer an excellent set of algorithmic problems that you can practice on. It’s recommended to try at least one problem per day, leading up to an interview. This will give you a fresh mindset for problem solving and hopefully have you prepared for any technical discussion you might come across.
While refreshing your knowledge, you may also want to review the technique of map-reduce, for working with large data sets and computations across multiple sources (for example, determining the prime divisors for a set of numbers). Other topics to review include understanding the differences between locks, mutexes, semaphores, deadlocks, and livelocks. Further practice should also include a review of software application scalability (architecting an application through a web application layer, load balancers, REST service layer, and database; followed by offloading traffic with static content, content delivery networks (CDN), Amazon S3 and Cloudfront access, as well as caching, batch jobs, and client-based code for data or calculation intensive processing).
This article was written by Kory Becker, software developer and architect, skilled in a range of technologies, including web application development, artificial intelligence, machine learning, and data science.