Hey Guys,

Hope you’re having an awesome day!

We’re going to be switching around the ordering today. The previous solution will be first and the interview problem will be last.

Previous Solution

As a refresher, here’s the last question

You are given the root to a binary search tree.

Find the second largest node in the tree and return it.

Solution

The brute force solution there would be to just do an in-order traversal of the tree.

Then, when we have a list of all the ordered nodes in the tree, we can just return the second largest element in the list.

This solution takes O(n) time and space. Can we do better?

We can!

Let’s say the problem said find the second smallest node in the tree and return it. How would we do that? Well, we could just quit our in-order traversal once we’ve visited two nodes!

However, our problem statement is the second largest node in the tree. So, how can we modify our inorder traversal to solve this variant with the same approach?

We reverse our inorder traversal!

With inorder traversal, we

1. Traverse the left subtree

2. Process the node

3. Traverse the right subtree

We’ll reverse it! In a reverse in-order traversal, we

1. Traverse the right subtree

2. Process the node

3. Traverse the left subtree

In a Binary Search Tree, reverse in-order traversal will give us the nodes sorted in largest-to-smallest order!

Now, we can just quit once we’ve processed two nodes and return the second largest node in our tree.

Here’s the Python 3 code.

Industry News

One More Apple Event?

Apple has announced a third Fall 2020 event which will be on November 10th.

Apple is expected to unveil the first Apple Silicon Mac with an ARM-based chip. Until now, Apple has used Intel CPUs in their Macintosh computers but Apple recently announced a switch to processors that are built in-house.

In-house built processors add quite a few advantages for performance and battery life.

Other products that could be unveiled are

• AirTags - Apple’s rumored Bluetooth trackers that can attach to items like wallets or pet collars. This allows them to be tracked in the Find My app alongside your iPhone or iPad.

• AirPod studio - Apple’s AirPods have been a massive success. Apple has expanded the lineup with AirPod Pro, a premium in-ear headphone. Apple has also been rumored to be working on an over-ear headphone called the AirPod Studio. The rumors suggest that AirPod Studio will be priced at $350 and will offer Active Noise Cancellation.

I’ve gotten some feedback that the emails are too long. Do you guys want more industry news? Less? Please reply to this email with any feedback. Thank you!

Interview Problem

Given a binary tree, determine whether or not the tree is height-balanced.

Reply to this email with your thoughts on how you’d solve this to be entered into our raffle to get a $100 dollar Amazon Gift Card or a Mock Google Coding Interview (your choice!)

You’ll get 1 - 4 points depending on how detailed your reply is (each point is an entry into our raffle).

You will ALWAYS get at least 1 point for replying!