Skip to main content

Binary Trees and Tries

Overview​

This lesson covers three similar, tree-based data structures:

  • Binary trees.
  • Tries.
  • A self-balancing binary tree (aka, an AVL tree).

There are four components to this lesson. We recommend tackling them in the order below:

  1. myGA Module 1: Binary Trees and Tries
    • If the above link does not take you to the correct module, you can find the lesson in your myGA dashboard.
  2. In-Class Exercise: Implementing a Binary Tree
  3. myGA Module 2: Balancing a Binary Tree
    • If the above link does not take you to the correct module, you can find the lesson in your myGA dashboard.
  4. In-Class Exercise: Implementing an AVL Tree

The myGA modules contain a link to an exercise in CodePen. The code in CodePen is the exact same as the code in the in-class exercises. Try out the exercise in CodePen and see how far you can get with it. Stop when you get stuck and we'll review the solution in class.

Learning Objectives​

By the end of this lesson, you'll be able to:

  • Describe how a binary tree is structured and what makes it powerful.
  • Describe how a trie is structured.
  • Identify scenarios in which trees are used in programming.
  • Balance a binary tree.

Prerequisites​

  • Big O notation
  • Recursion

Duration​

3 hours total:

  • 1 hour myGA
  • 2 hours in class

Additional Resources​

  • Since we don't cover how to build a trie, read about how it's implemented in code here.