In the previous lesson of this recurion and trees course, we learned about recursion and how it naturally describes a tree data structure. In this lesson, we are going to explore a type of tree called a binary tree. We’ll start our investigation of trees with binary trees first because they are the easiest to define, and are commonly used in practical applications.

As this lesson progresses, we'll discuss what a binary tree is, the parts of a binary tree, why they're useful, how to traverse a binary tree, and more! We’ll talk about multiple inserts, differentiate between interior, child, and parent nodes, and then spend some time practicing traversing the tree and finding total nodes and depth.

Binary trees can be difficult to grasp at first, but a binary tree is a very efficient data structure for finding data. And as with all Dataquest courses, you’ll be able to apply what you’re learning step-by-step inside your browser as you progress through each screen of this lesson by writing your own code and having it checked by our automated answer-checker.

Objectives

  • Learn about the binary tree structure.
  • Learn how common algorithms used on binary trees.

Lesson Outline

1. Introduction
2. Multiple Inserts
3. Interior, Child, and Parent Nodes
4. Traversing the Tree
5. Finding Total Nodes and Depth
6. Types of Trees
7. Next Steps
8. Takeaways