…and, an introduction to recursion methods

Last week we began our introduction into the binary search tree. In Ruby, we set-up our Node Class and our BinarySearchTree Class and implemented the #insert method. Today, we are going to code the #find method which will give us some better insight into how a binary search tree is traversed. However, today we will also begin to look at a method using recursion.

First, a brief recap: A binary search tree is a data structure that is organized in such a way that each element (or Node) contains no more than two child nodes (hence the term “binary”). The…


According to Algorithms (4th Edition) by Robert Sedgewick and Kevin Wayne, a binary search tree (BST) is “a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node’s left subtree and smaller than the keys in all nodes in that node’s right subtree.”

Trees are a bit of a departure from the more strictly horizontal or vertical data structures we have been working with so far like Linked Lists and Stacks/Queues. Lists are linear. …


Any English speaker who as traveled to other English speaking regions has had the experience of encountering words that are sounded and spelled the same way but have different uses depending on your locality. Two words that come to mind right away are “mate” and “lift.” In the New York version of English of which I’m most familiar, these two words are verbs. To my friends in London, these two words are nouns. The context of the usage of these words often clarifies the discrepancy before too long. …


Photo by Melanie Pongratz on Unsplash

Coming from a theater background, my concept of queue revolved around what lighting pattern was executed or what sound design file was to play when the stage manager said, “Standby for lighting cue 7 and sound cue G.” When I heard the stage manager say, “Go,” I was to execute the proper lighting and sound design pattern. In 2003, I found myself working a show at the Edinburgh Festival in Scotland. The first thing I was told when I got off the plane was, “Go queue-up at passport control.” Jet-lagged and hungry, it took me a moment to understand that…


A stack is a simple data structure that follows the principle, “Last In, First Out.” Unlike many terms used in computer science, this one actually says what it is: A stack. Think of a stack of papers. If you piled the bills you received in the mail on a table one on top of the other as you received them each day, you would have a stack of bills. Let say you did this all month, and at the end of the month, you went to pay them all. You may simply begin at the top of the pile of…


Last week we looked at Singly Linked Lists in Ruby with examples of how to set up the class structures as well as exploring some common methods. Today, we will continue our discussion of data structures in Ruby with Doubly Linked Lists.

The main difference between Singly Linked Lists and Doubly Linked Lists is the fact that nodes in a Singly Linked List have only one pointer, next, whereas the nodes in a Doubly Linked List have two pointers: next and previous which point to their adjacent respective Nodes. This difference gives Doubly Linked Lists a time efficiency advantage when…


In the previous post, we set up our Node Class as well as our SinglyLinkedList Class, including the initialization and a few basic methods: #push, #pop, #shift, and #unshift. Now we will expand on our collection of methods for viewing and manipulating our Singly Linked List (from now on: SLL).

It comes as no surprise that there may be times that we would want to check what is populated in our list at certain index points. The first common method for this is #get, which takes in an index as an argument and returns the Node at that particular index…


Although computer science majors will probably learn data structures and algorithms in a language like C, C++, Java, or Python, I first learned Ruby as the backend language and JavaScript for everything else. Since the course I used to learn data structures and algorithms used JavaScript to teach the examples, I thought I’d return to my roots and set-up a workable Singly Linked List data model that can be used in place of arrays for one’s data needs. …


#radix_sort

One of the beautiful things about Radix Sort is that of the basic sorting algorithms it sits on the low end of Big O. Generally speaking, its time complexity in both the best and worst case scenarios is O(nk), where n is the size of the array and k is the amount of digits in the array’s largest integer. It keeps the time complexity low because the algorithm avoids any direct comparison between any of the components of the array and therefore removes the need for any nested loops. The most basic description I can give of radix sort is…


Since graduating from a software engineering coding bootcamp I have been spending most of my time getting a handle on the basics of computer science, specifically data structures and algorithms. Today I wanted to share the experience of the naïve string search since this has as its basic real-world implementation a crude text searching feature that one could use on their web site (with JavaScript on the frontend) or for searching through some long text storage in their database (with Ruby for the backend).

One thing I noticed about this string searching algorithm as the way it is often taught…

Anthony Lepore

Composer, playwright, designer for theater, jazz musician, philosopher. Recent Software Engineer graduate of Flatiron School in NYC.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store