Overview

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

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

Prerequisites

• Big O Notation
• Recursion

Learning Objectives

By the end of this module, learners will be able to:

• Describe how binary trees and tries are structured.
• Determine whether breadth-first or depth-first traversal is a more efficient search method for a given situation.
• Identify scenarios in which binary trees and tries are used in programming.
• Implement a binary tree.
• Distinguish between a balanced and an unbalanced binary tree.
• Explain how an AVL tree balances itself.
• Balance a binary tree.

Content

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

1. Lesson: Binary Trees and Tries
2. Exercise: Implementing a Binary Tree
3. Lesson: Balancing a Binary Tree
4. Exercise: Implementing an AVL Tree

Solution Code

• Exercise Solution: Implementing a Binary Tree
• Exercise Solution: Implementing an AVL Tree

Time to Complete

3 hours total:

• 1 hour - Binary Trees and Tries and Balancing a Binary Tree Lessons
• 2 hours - Implementing a Binary Tree and Implementing an AVL Tree Exercises

Additional Resources

• Since we don’t cover how to build a trie, read about how it’s implemented in code here.
• Check out these beautiful visualizations: a binary tree, a trie, and an AVL tree.
• How to distinguish between several types of tree data structures.
• Common interview questions about binary trees.
• Tree balancing interview prep: here and here.
• Whiteboarding an AVL tree.

Internal resources

✏️ Instructor Guide

🏗️ Release Notes

---

Find a 👾 bug 👾 or have suggestions? Let us know!