Project: Data Structures and Algorithms

Project 1: Binary Search Trees

You learned about binary search trees – where you take a group of data items and turn them into a tree full of nodes where each left node is “lower” than each right node. The tree starts with the “root node” and any node with no children is called a “leaf node”.

You also learned about tree traversal algorithms like breadth-first and depth-first which we’ll attempt to implement here.

Assignment 1

You’ll build a simple binary search tree in this assignment. In this lesson, our tree won’t handle duplicate values as they are more complicated and result in trees that are much harder to balance. Be sure to always remove duplicate values or check for an existing value before inserting.

1. Build a `Node` class. It is should have attributes for the data it stores as well as its left and right children. As a bonus, try including the `Comparable` module and make nodes compare using their data attribute.

2. Build a `Tree` class which accepts an array when initialized. The `Tree` class should have a `root` attribute which uses the return value of `#build_tree` which you’ll write next.

3. Write a `#build_tree` method which takes an array of data (e.g. [1, 7, 4, 23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]) and turns it into a balanced binary tree full of `Node` objects appropriately placed (don’t forget to sort and remove duplicates!). The `#build_tree` method should return the level-1 root node.

4. Write an `#insert` and `#delete` method which accepts a value to insert/delete (you’ll have to deal with several cases for delete such as when a node has children or not).

5. Write a `#find` method which accepts a value and returns the node with the given value.

6. Write a `#level_order` method which accepts a block. The method should traverse the tree in breadth-first level order and yield each node to the provided block. This method can be implemented using either iteration or recursion (try implementing both!). As a bonus, make the method return an array of values if no block is given. Tip: You will want to use an array acting as a queue to keep track of all the child nodes that you have yet to traverse and to add new ones to the list (as you saw in the video).

7. Write `#inorder`, `#preorder`, and `#postorder` methods which accept a block. Each method should traverse the tree in their respective depth-first order and yield each node to the provided block. As a bonus, make the method return an array of values if no block is given.

8. Write a `#depth` method which accepts a node and returns the depth(number of levels) beneath the node.

9. Write a `#balanced?` method which checks if the tree is balanced. A balanced tree is one where the difference between heights of left subtree and right subtree is not more than 1.

10. Write a `#rebalance!` method which rebalances an unbalanced tree. Tip: You’ll want to create a level-order array of the tree before passing the array back into the `#build_tree` method.

11. Write a simple driver script that does the following:

``````1. Create a binary search tree from an array of random numbers (`Array.new(15) { rand(1..100) }`)
2. Confirm that the tree is balanced by calling `#balanced?`
3. Print out all elements in level, pre, post, and in order
4. try to unbalance the tree by adding several numbers > 100
5. Confirm that the tree is unbalanced by calling `#balanced?`
6. Balance the tree by calling `#rebalance!`
7. Confirm that the tree is balanced by calling `#balanced?`
8. Print out all elements in level, pre, post, and in order
``````

Pat yourself on the back! As a super-duper bonus, notice how all the depth-first methods share a similar signature and are basically just a re-arrangement of the same 3 lines… try dynamically declaring the three methods using metaprogamming techniques like `#define_method`.

Student Solutions

Submit a link below to this file on the ruby course github repo with your files in it by using a pull request. See the section on Contributing for how.

Show Student Solutions

Project 2: Knight’s Travails

Now you’re a pro with DFS and BFS. Let’s try using our search algorithms on a real problem.

For this project, you’ll need to use a data structure that’s similar (but not identical) to a binary tree. For a summary of a few different examples, reference this article.

A knight in chess can move to any square on the standard 8x8 chess board from any other square on the board, given enough turns (don’t believe it? See this animation). Its basic move is two steps forward and one step to the side. It can face any direction.

All the possible places you can end up after one move look like this:

Assignment 2

Your task is to build a function `knight_moves` that shows the simplest possible way to get from one square to another by outputting all squares the knight will stop on along the way.

You can think of the board as having 2-dimensional coordinates. Your function would therefore look like:

• `knight_moves([0,0],[1,2]) == [[0,0],[1,2]]`
• `knight_moves([0,0],[3,3]) == [[0,0],[1,2],[3,3]]`
• `knight_moves([3,3],[0,0]) == [[3,3],[1,2],[0,0]]`
1. Put together a script that creates a game board and a knight.
2. Treat all possible moves the knight could make as children in a tree. Don’t allow any moves to go off the board.
3. Decide which search algorithm is best to use for this case. Hint: one of them could be a potentially infinite series.
4. Use the chosen search algorithm to find the shortest path between the starting square (or node) and the ending square. Output what that full path looks like, e.g.:
``````  > knight_moves([3,3],[4,3])
=> You made it in 3 moves!  Heres your path:
[3,3]
[4,5]
[2,4]
[4,3]
``````

Student Solutions

Send us your solution so we can show others! Submit a link to the Github repo with your files in it here using any of the methods listed on the contributing page. Please include your partner’s github handle somewhere in the description if they would like attribution.

Show Student Solutions

Ruby Programming

Project: Data Structures and Algorithms

Have a question?

Chat with our friendly Odin community in our Discord chatrooms!

Thinkful

• 5-6 months

• Job Guarantee

• 1-on-1 Mentorship