Python Data Structures: Trees

1h 17mIntermediate2021-02-25

Authors

Ryan Mitchell

Senior Software Engineer at GLG

Course details

What are trees, in Python, and how do they fit in with other data structures such as linked lists and graphs? In this course, instructor Ryan Mitchell discusses binary search trees (BSTs) and what you can do with them in a real-world context. Ryan shows you how to build a basic tree with just a few lines of Python. She steps through how to search and traverse a tree, as well as how to print a tree to a terminal. Ryan explains how to add nodes to your tree, delete them, and detect unbalanced trees. When you find an unbalanced tree, it’s important to rebalance it. Ryan walks you through rebalancing four types of unbalanced trees. She concludes with a challenge that features smarter automated rebalancing.

Skills covered

Data EngineeringPythonProgramming LanguagesData ScienceOpen SourceSoftware DevelopmentOne-Off

Concepts

0. Introduction

01 - Getting started with trees
02 - What you should know
03 - BSTs and other trees

1. Navigating Trees

04 - Building a basic tree
05 - Searching a tree
06 - Traversing a tree
07 - Getting the maximum height of a tree
08 - Getting all nodes at a particular depth
09 - Challenge - Printing a tree
10 - Solution - Printing a tree

2. Modifying Trees

11 - Adding nodes
12 - Deleting nodes - Theory
13 - Deleting nodes - Code
14 - Detecting unbalanced trees
15 - Challenge - Adding a balance indicator to the printed tree
16 - Solution - Adding a balance indicator to the printed tree

3. Rebalancing Trees

17 - Introduction to rotations
18 - Rotating trees in Python
19 - Fixing a tree with multiple points of imbalance
20 - Challenge - Smarter automated rebalancing
21 - Solution - Smarter automated rebalancing

Conclusion

22 - Next steps with data structures