3 years ago

# Binary Search Trees, Traversals and Balancing in Python

### Part 2 of "Data Structures and Algorithms in Python"

Data Structures and Algorithms in Python is beginner-friendly introduction to common data structures (linked lists, stacks, queues, graphs) and algorithms (search, sorting, recursion, dynamic programming) in Python, designed to help you prepare for coding interviews and assessments. Check out the full series here:

1. Binary Search and Complexity Analysis
2. Binary Search Trees, Traversals and Balancing
3. Python Classes and Linked Lists
4. Stacks, Queues and Strings (coming soon)
5. Insertion Sort, Merge Sort and Divide-and-Conquer (coming soon)
6. Quicksort, Partitions and Average-case Complexity (coming soon)
7. Recursion, Backtracking and Dynamic Programming (coming soon)
8. Knapsack, Subsequence and Matrix Problems (coming soon)
9. Graphs, Breadth-First Search and Depth-First Search (coming soon)
10. Shortest Paths, Spanning Trees & Topological Sorting (coming soon)
11. Disjoint Sets and the Union Find Algorithm (coming soon)
12. Interview Questions, Tips & Practical Advice (coming soon)

Earn a verified certificate of accomplishment for this course by signing up here: http://pythondsa.com .

Ask questions, get help & participate in discussions on the community forum: https://jovian.ai/forum/c/data-structures-and-algorithms-in-python/78

#### Prerequisites

This course assumes very little background in programming and mathematics, and you can learn the required concepts here:

We'll cover any additional mathematical and theoretical concepts we need as we go along.

### How to Run the Code

The best way to learn the material is to execute the code and experiment with it yourself. This tutorial is an executable Jupyter notebook. You can run this tutorial and experiment with the code examples in a couple of ways: using free online resources (recommended) or on your computer.

##### Option 1: Running using free online resources (1-click, recommended)

The easiest way to start executing the code is to click the Run button at the top of this page and select Run on Binder. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

##### Option 2: Running on your computer locally

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

### Problem

In this notebook, we'll focus on solving the following problem:

QUESTION 1: As a senior backend engineer at Jovian, you are tasked with developing a fast in-memory data structure to manage profile information (username, name and email) for 100 million users. It should allow the following operations to be performed efficiently:

1. Insert the profile information for a new user.
2. Find the profile information of a user, given their username
3. Update the profile information of a user, given their usrname
4. List all the users of the platform, sorted by username

You can assume that usernames are unique.

Along the way, we will also solve several other questions related to binary trees and binary search trees that are often asked in coding interviews and assessments.

### The Method

Here's a systematic strategy we'll apply for solving problems:

1. State the problem clearly. Identify the input & output formats.
2. Come up with some example inputs & outputs. Try to cover all edge cases.
3. Come up with a correct solution for the problem. State it in plain English.
4. Implement the solution and test it using example inputs. Fix bugs, if any.
5. Analyze the algorithm's complexity and identify inefficiencies, if any.
6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.