Learn How to Code
  • Welcome
  • Foundations
    • Introduction
      • Becoming a web developer
      • Motivation and mindset
      • Join a supportive community
      • How does the web work?
    • Requirements
      • Prerequisites
      • Text editors
      • Command line basics
      • Setting up Git
      • Setting up Node
    • Git
      • Git basics
      • Project: Practicing Git
    • Frontend
      • HTML and CSS
      • Developer Tools
      • Project: Create a web page
    • JavaScript
      • Strings and Conditionals
      • Using Developer Tools
      • Functions
      • Problem solving
      • Project: Rock paper scissors
      • Writing clean code
      • Arrays and Loops
      • The DOM
      • Project: Etch-A-Sketch
      • Objects and More Arrays
      • Project: Calculator
    • Backend
      • Frameworks
    • Next steps
  • Deep dives
    • Computer Science
      • Pseudocode and algorithms
      • Recursion and algorithms
        • Project: Fibs and sorting
        • More on algorithms
        • Big O
        • Project: Practicing Big O
      • Data structures
        • Maps, Stacks and Queues
        • Project: Stacks and Queues
        • Nodes, Linked Lists and Trees
        • Project: Linked Lists
        • Project: Trees
        • Next steps
    • Databases
      • Databases and SQL
      • Project: SQL Zoo
    • Design / UX
      • Fonts and typography
      • Grids
      • Project: Teardown
      • Responsive design
      • Project: Mobile friendly
      • CSS frameworks
      • Project: Bootstrapping
    • HTML / CSS
      • HTML Basics
        • Linking
        • Images and media
        • Project: Embedding media
        • HTML5
        • Tables
        • Lists
        • Forms
        • Project: Make a form
      • CSS Basics
        • Box model
        • Floats and positioning
        • Flexbox
        • Grids
        • Project: Breaking news
        • Best practices
        • Backgrounds and gradients
        • Project: One more thing
        • CSS3
        • Preprocessors
        • Project: Your own framework
      • Next steps
    • JavaScript
      • Refresher
      • Organization
      • Objects and constructors
      • Project: Library
      • Factory functions and module patterns
      • Project: Tic Tac Toe
      • Classes
      • ES6 Modules
      • Project: Restaurant
      • Object Oriented Programming
      • Project: Todo list
      • Linting
      • Menus and sliders
      • Forms
      • ES6 features
      • JSON
      • Callbacks and promises
      • Using APIs
      • Async and Await
      • Project: Weather
      • Testing
      • Project: Testing 1-2-3
      • Advanced Testing
      • Project: Battleship
      • Backends
      • Project: Where's Waldo?
      • Project: All-Star
      • Next steps
    • NodeJS
      • Project: Going to school
      • Project: Passing the test
      • Express
        • Templates and middleware
        • CRUD and MVC
        • Project: Message board
        • Routes
        • Displaying data
        • Forms and deployment
        • Project: Inventory
      • Authentication
      • Security
      • Project: Clubhouse
      • APIs
      • Securing an API
      • Project: Blog
      • Testing
      • Testing with a database
      • Project: Social network
    • React
      • Props and State
      • Render lists and handle inputs
      • Project: CV
      • Lifecycle methods
      • Hooks
      • Project: Memory card
      • Router
      • Project: Shopping cart
      • Advanced concepts
    • Ruby
      • Installation
      • Data types
      • Variables
      • Input and Output
      • Conditionals
      • Loops
      • Arrays
      • Hashes
      • Methods
      • Enumerables
      • More enumerables
      • Nested collections
      • Blocks
      • Pattern matching
      • Debugging
      • Project: Caesar cipher
      • Project: Substrings
      • Project: Stock picker
      • Project: Bubble sort
      • Object oriented programming
      • Project: Tic Tac Toe
      • Project: Mastermind
      • Serialization
      • Project: Event manager
      • Project: Hangman
      • Computer Science
        • Recursion
        • Project: Merge Sort
        • Data structures and algorithms
        • Project: Linked Lists
        • Project: Binary Search Trees
        • Project: Knight Travails
      • Testing
      • RSpec
      • Project: Four in a row
      • Git
      • Project: Open Source
      • Project: Chess
      • Next steps
    • Ruby on Rails
      • Using Heroku
      • Installing Rails
      • Basics
        • Routing
        • Controllers
        • Views
        • Asset pipeline
        • Deployment
        • Project: Blog
      • Active Record
        • Project: Upvote
      • Forms
        • Cookies, sessions, and authentication
        • Project: Password
      • Advanced forms and Active Record
        • Associations
        • Project: Private Events
        • Callbacks
        • Menus, helpers and nested forms
        • Project: Ticket agent
      • APIs
        • External APIs
        • Project: Animals
        • Project: Photo widget
      • Mailers
        • Project: Confirmation
      • Advanced topics
        • Action Cable
      • Project: Social network
      • Next steps
  • Getting hired
    • Preparing to find a job
      • Plan a strategy
      • What companies want
      • Get yourself together
      • How to prepare
      • Project: Make your website
    • Applying and interviewing
      • Qualifying leads
      • Project: Make your resume
      • Applying for jobs
      • Preparing for an interview
      • Handling an offer
      • Final words
  • Maintained by
    • wbnns
  • License
    • CC BY-NC-SA 4.0 © 2022
Powered by GitBook
On this page
  • Introduction
  • Assignment
  1. Deep dives
  2. Ruby
  3. Computer Science

Project: Binary Search Trees

Learn how to build a balanced binary search tree.

PreviousProject: Linked ListsNextProject: Knight Travails

Last updated 4 years ago

Introduction

You have learned about -- 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 have also learned about tree traversal algorithms like breadth-first and depth-first.

Now, let's take a look at balanced binary search trees (BST). Read and watch to understand the basic algorithm used to build a balanced BST. Although these two resources do not use Ruby, you should understand it enough to develop your own pseudocode.

Assignment

You'll build a balanced BST in this assignment. Do not use duplicate values because they make it more complicated and result in trees that are much harder to balance. Therefore, be sure to always remove duplicate values or check for an existing value before inserting.

  1. Build a Node class. It should have an attribute for the data it stores as well as its left and right children. As a bonus, try including the Comparable module and compare nodes 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). If you need additional resources, check out these two articles on and , or with several visual examples.

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

  6. Write a #level_order method that returns an array of values. This method should traverse the tree in breadth-first level order. This method can be implemented using either iteration or recursion (try implementing both!). 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 ).

  7. Write #inorder, #preorder, and #postorder methods that returns an array of values. Each method should traverse the tree in their respective depth-first order.

  8. Write a #height method which accepts a node and returns its height. Height is defined as the number of edges in longest path from a given node to a leaf node.

  9. Write a #depth method which accepts a node and returns its depth. Depth is defined as the number of edges in path from a given node to the tree's root node.

  10. 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 of every node is not more than 1.

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

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

    • Create a binary search tree from an array of random numbers (Array.new(15) { rand(1..100) })

    • Confirm that the tree is balanced by calling #balanced?

    • Print out all elements in level, pre, post, and in order

    • Try to unbalance the tree by adding several numbers > 100

    • Confirm that the tree is unbalanced by calling #balanced?

    • Balance the tree by calling #rebalance

    • Confirm that the tree is balanced by calling #balanced?

    • Print out all elements in level, pre, post, and in order

Tip: If you would like to visualize your binary search tree, here is a #pretty_print method:

def pretty_print(node = @root, prefix = '', is_left = true)
  if node.right
    pretty_print(node.right, "#{prefix}#{is_left ? '│   ' : '    '}", false)
  end
  puts "#{prefix}#{is_left ? '└── ' : '┌── '}#{node.data}"
  if node.left
    pretty_print(node.left, "#{prefix}#{is_left ? '    ' : '│   '}", true)
  end
end
binary search trees
this article
this video
inserting
deleting
this video
video