Summary

The article discusses a common technical interview question for Amazon and Microsoft candidates, focusing on validating a binary search tree (BST) both recursively and iteratively.

Abstract

The article addresses a technical interview question that has been prevalent in recent Amazon and Microsoft phone screens, which involves validating a binary search tree (BST). It explains the properties of a BST, where each node's left subtree contains only nodes with keys less than the node's key, and the right subtree contains only nodes with keys greater than the node's key. The article provides a detailed walkthrough of two approaches to solve this problem: a recursive method that uses "floor" and "ceiling" values to validate subtrees, and an iterative method that leverages in-order traversal to ensure the tree's values are ordered correctly. The recursive solution has a time complexity of O(N) and a space complexity of O(N) due to the recursion stack, while the iterative solution also has a time complexity of O(N) but uses a stack to achieve the traversal, maintaining the same space complexity. The article concludes by inviting readers to follow the author for more content and to suggest topics for future articles.

Opinions

The author emphasizes the importance of understanding the BST properties thoroughly to solve the problem effectively.
The recursive approach is presented as a method that requires careful consideration of the "floor" and "ceiling" values to ensure the validity of the BST.
The iterative approach is suggested as a simpler alternative that relies on the inherent ordering of values in a BST during an in-order traversal.
The article suggests that the iterative solution is more intuitive, as it directly checks the ordering of values without the need for additional parameters like "floor" and "ceiling."
The author encourages readers to engage with their content by following them on Medium and suggesting future topics, indicating a desire to build a community and provide value to aspiring software engineers.

Can you solve this Amazon and Microsoft technical interview question? Validating a Binary Search Tree

This question was commonly asked in Amazon and Microsoft technical phone screens in the last few months.

Here’s the question:

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.

The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Here are the examples:

We’l walk through two ways of solving this: recursively and using a tree traversal.

Recursively

Intuition

At each node, we need to check:

- Is the left value smaller than the root?

- Is the right value larger than the root?

But, it’s more complicated than that! For example, what if the above two conditions are true, but the right value is actually larger than the top-level root? This breaks the binary search tree invariant!

Here’s an example:

100 is on the right of the 1 node, but greater than 1’s parent node, 5! This isn’t a valid binary search tree.

So we actually need to pass down some global values — what are the smallest and largest values for a given subtree?

Framework

If we use this framework of having a “floor” and a “ceiling” value, this problem becomes easier to reason about.

Let’s say we’re looking at our current root. Then we know everything to the left must be smaller than the root, so I’ll pass a “ceiling’ value in — if the left node has a value greater than this ceiling, I know this isn’t a valid tree.

Similarly, if we look at the right subtree, I’ll pass a “floor” ceiling in — everything on the right subtree must be greater than this value.

Note when I’m looking at the left subtree, I don’t need to update the “floor” value — the left subtree doesn’t have a *minimum* value. Similarly when I’m looking at the right subtree, I don’t need to update the “ceiling” value — the right subtree doesn’t have a *maximum* value yet.

Importantly though, note that when we’ve gone down the left subtree, then visited the “right” side of that subtree, there *is* a ceiling value! So we’re bounding the value of what the subtree can have.

Let’s take a look at the code:

So our first call we pass in infinity as the ceiling and -infinity as the floor, because there aren’t any restrictions yet.

Algorithmic Complexity

The runtime of this solution is O(N) to traverse the tree. The space complexity of this solution is also O(N) for the recursion stack.

Iteratively

Observation

The key observation is that if we do an in-order traversal of a binary search tree, the values will be ordered. Let that sink in and make sure you can reason about why that is!

So a really simple way of solving this is to just do the in-order traversal and assert that the output is ordered.

However, because we’re generating the output step by step, we can actually just look at the value we just appended, and see if that value is less than the value we’re *about* to append.

If that isn’t true, then we know that this isn’t a valid binary search tree.

Let’s take a look at the code.

Algorithmic Complexity

The runtime of this solution is O(N) to traverse the tree. The space complexity of this solution is O(N) for the stack.

Hope this helps and let me know if there’s any other problem you want me to explain.

For more articles like this, follow me on Medium. Not a member yet? Join the community. Want more software engineering interview guides and coding question tips? Check out all of my writing organized by topic in this article.

If you have any requests for what I should write, please let me know!