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…

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

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

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…

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