#Code Challenge #5: May 10, 2017

Every week, we feature the type of brain-teasing question that might be asked in a full-stack developer’s job interview at places such as Google and Facebook.

This week’s challenge was reportedly asked in interviews at **Google** (and even in some other contexts that you may not expect):

###The Challenge

You are given a list of numbers stored in a list,

`A`

. Your challenge is to build a [Binary Search Tree] (https://en.wikipedia.org/wiki/Binary_search_tree) to store these numbers. You will need to:

- Represent each node of the tree (including its data, left child and right child).

- Print the tree out in an understandable form.
- Make a function to insert a list of numbers (
`A`

) into the tree.

Check if you can insert all the numbers in

`A`

into your tree, and that it prints out as expected.

*Use the language of your choice to solve this challenge, but only submissions in languages taught by Codecademy are eligible to “win”.*

###Intermediate difficulty

Write a function to check if the Binary Search Tree that you’ve created is balanced.

*A tree is considered balanced when the difference between the min depth and max depth does not exceed 1, i.e. if the list had n elements in it the height of the tree would be log(n) (base 2).*

#####Find out more about intermediate challenges.

###Hard Difficulty

- Adapt your function to insert a list of
`n`

numbers so that it runs in`O(n log n)`

time. Bear in mind that this is just the average case for a random sequence of numbers. If the list`A`

was sorted it would take`O(n^2)`

.

- Adapt your function to check if the tree is balanced so that it runs in
`O(n)`

time.

*If your BST is balanced then the insert function would have only taken O(n log n) time, see if you can figure out why.*

## #####Find out more about hard challenges and Big O

###Winner

@tagrockstar79958 was the first to submit a complete working solution at the hard difficulty level: see it here.

###How to Participate

If you want to add your own submission to this challenge, you are more than welcome to do so – it will help you to practice and help everyone else to learn! Simply scroll down and ** reply to this thread with your code** to participate! Don’t just submit your code, remember to

`explain`

your solution, too! If you want your entry to be considered under our “best code” assessment, you must include a link to your code running on repl.it and abide by our other simple rules.**The fine print:**

Click the links to find out more about:

- the rules & how to participate in challenges
- how challenges are used as job interview questions
- why Codecademy runs challenges (and why they are formatted this way)
- more details about the challenges and why we think they are useful.
- find previous challenges (and see the past winners) in our Challenge Index