Photo by Flavio Takemoto
Photo by Flavio Takemoto

I am going to start off by saying that this is the fastest searching algorithm with a few caveats. For starters, the data structure that is being search through needs to be sorted. Also, there are some nuances regarding some other algorithms that may search quicker depending on how evenly distributed the sorted data is. But for the most part, if you are looking for an element in a data structure (such as an array) that is already known to be sorted, it is tough to do better than Binary Search.

To illustrate the concept behind Binary Search, I’ll show…


We have now come of the final of the three main types of Depth-First Search (DFS) for a Binary Search Tree: In-Order traversal. DFS In-Order, as far as I am concerned, is probably the most useful as the return values are delivered as a sorted array from lowest to highest value.

First, a very brief recap of what we covered so far for Binary Search Tree traversals:

· A Binary Search Tree is a data structure wherein each node has at most two child-nodes (hence the term Binary)

· The child node to the left is always smaller than the…


Last week we introduced the concept of Depth-First Search for Binary Tree traversals. Of the three main types of Depth-First Search (DFS) algorithms, we began with a pre-order search, which begins at the root node of the binary tree and returns each node visited on the way down the left side of the tree, then down the right side of the tree. Like our discussion of Breadth-First Search, the root node is the first value returned in a pre-order DFS. In a Depth-First Search Post-Order algorithm, the first value in our returned list would be the deepest node on the…


In continuing with our current topic of binary tree traversals in Ruby, we are going to introduce depth-first search this week. If you recall from the last article on breadth-first search, a traversal through a binary tree should be accomplished by visiting each node on the tree only once. That part of the tree traversal should remain a constant. But since trees are non-linear data structures, what is the best way to return all the nodes on the tree in an efficient manner? That is going to depend on what you want the return order to look like. In the…


Solution using our custom Queue Class

Last week, we implemented a #find method for our Binary Search Tree which returned the Boolean true/false indicating whether our value was found or not. What if we wanted to return all the nodes in our Binary Search Tree? Look at a representation of any Binary Tree (it doesn’t even have to be a Binary Search Tree). If you were asked to write some code to return all the values in this binary tree while visiting each node only once, how would you do it? …


…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…

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