How to Formulaically Solve Tree Interview Questions · Daily Coding Problem
Tree questions are very common at top tech company interviews. I had two tree questions in my Google onsite interviews and one during my Facebook onsite interviews. An awesome thing about them is that they can be formulaically solved every single time. It doesn't involve any genius insight. Let me show you how.
Instead of being too abstract, let's just dive right into an easy binary tree question. Then I'll walk through how to solve it and we can go into a harder problem after:
Given the root to a binary tree, count the total number of nodes there are.
Before we move on further, feel free take a moment to think about the answer!
Solving any binary tree question involves just two steps.
First is solving the base case. This usually means solving the leaf node case (a leaf node has no left or right children) or the null case. For the above problem, we can see that a null should represent 0 nodes while a leaf node should represent 1 node.
Second is the recursive step. Assuming you knew the solution to the left subtree and the right subtree, how could you combine the two results to give you the final solution? It's important to not get caught up on how this works and just have faith that it works. If you start tracing the recursion, you're going to needlessly use up time and energy during the interview. Intuitively though, it works for similar reasons as why regular induction works. P(0) or the base case works which causes P(1) or the leaf node to work which causes P(2) to work and so on. For this problem, it's easy to combine the results of the left and right subtrees. Just add the two numbers and then another 1 for the root. Here's the code:
Read full article from How to Formulaically Solve Tree Interview Questions · Daily Coding Problem
No comments:
Post a Comment