Ace Your Coding Interview — Blind 75 Solved and Explained — Part 6.1 Trees

8 min readJul 11, 2022

Moving on to what I believe to be the most important chapter, I will break it down into 2 sections. For this section, I will walk through the first 7 questions and finish the remaining 6 questions in part 2.

However, before attempting these questions learning a few core concepts in trees are imperative to best approach the questions. Otherwise, it’s exponentially harder to figure out the correct approaches.

Data Structures & Techniques:

Binary Search Tree
Depth First Search
Breadth-First Search
Trie
PreOrder, InOrder, and PostOrder Sorting
Recursion

Understanding these data structures and algorithms will allow us to solve the problems with the correct approaches. Some of these questions were personally hard to figure out and my solutions weren’t optimal I have linked solutions that I use in this tutorial that are completely from the leetcode discussion that I believe make the most sense.

As always the link to the original Blind 75 is below:

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

www.teamblind.com

Question 1 — Maximum Depth of Binary Tree

Maximum Depth of Binary Tree - LeetCode

leetcode.com

The solution from: https://leetcode.com/problems/maximum-depth-of-binary-tree/discuss/34216/Simple-solution-using-Java

Our Approach:

If our root is empty we return 0 because there is no depth.
We recursively check left and right subtrees, every time we do this we add one to our max depth as we know the roots to be not empty.

Question 2 — Same Tree

Same Tree - LeetCode

leetcode.com

Our Approach:

For trees to be the same, nodes have to match. We check if both tree nodes are empty. If both are empty, then we found two identical trees.
If one tree is empty and one isn’t they cannot be the same. Thus, we return false if only one is null and the other isn’t
We compare the values of each tree node, if equal we are going to keep checking for left and right subtrees.
If values don’t match, trees cannot be the same. Thus, we return false.

Question 3 — Invert/Flip Binary Tree

Invert Binary Tree - LeetCode

leetcode.com

Inverting a binary tree means we have to swap all the left-right and subtrees recursively. The best way to approach this is through a breadth-first search since it utilizes level-by-level traversal.

Our Approach:

Check if the root is empty, if so return null.
Declare a new queue that can be used to store the nodes. To start offer the root itself to the queue.
Next, we run the breadth-first search algorithm with some minor modifications. Each time we start we poll the contents of the queue.
The next step is the inverting of our tree: Swap the left and right nodes.
Once our swap occurs, we need to repeat this operation on our left and right subtrees. We need to offer the left and right nodes to our queue so the previous operation can be repeated. Before we add anything to the queue, make sure it isn’t null as it would cause a null pointer exception.

Question 4 — Binary Tree Maximum Path Sum

Binary Tree Maximum Path Sum - LeetCode

leetcode.com

A Solution to Binary Tree Maximum Path Sum

Solution from: https://leetcode.com/problems/binary-tree-maximum-path-sum/discuss/39875/Elegant-Java-solution

Our Approach:

We declare a global variable to keep track of our maximum path sum.
We create a helper method to find the max path sum.
As always, check to see if the root is null; if null, return zero as there can be no path sum.
After we check the root, we need to evaluate the left and right subtrees. During our left and right subtree evaluation, we need to account for negative values. If a negative value is found 0 is always a greater path sum. To account for this we add a Math.max() function.
After evaluating our subtrees, we need to update our global maximum. We compare our current maximum to the sum of left, right, and root nodes. This is because left → root → right forms a path itself.
We need to return the largest path value existent in a node. This is done by taking the root value and seeing if the right or left node is larger and adding that to the root. To visualize, work your way from the bottom up. For a path, we can only visit the left, root, and right nodes at the very root of the tree. As we move up towards the top we need to pick if the left or right side of each node provides a higher path sum.
Finally, we go back to the main method of our path sum. We call our helper method to calculate our max value.

Question 5 — Binary Tree Level Order Traversal

Binary Tree Level Order Traversal - LeetCode

leetcode.com

A Solution to Binary Tree Level Order Traversal

Our Approach:

Create a results list of lists to fill and return upon end of method
Check if the root is empty, if so return null.
Create a queue to add nodes into during breadth-first search.
Run a breadth-first search on our tree. This is done by iterating until our queue which holds nodes are empty.
We find the size of our current level, this is needed so we can loop through the items. This is done by checking the size of our queue as it represents all the nodes available inside it.
We create a simple list to hold onto our current level’s values. Once at the end of our list, we add this list to our results variable.
We iterate the amount of levels available to us. During this, we poll our queue to get the top element and add it to our current level. After we have added our current level, we need to prepare for the next one. This is done by checking the left and right subtrees to see if they posses valid nodes. If so, we add our subtrees to the queue to add for the next levels.
When the iterations of our levels are complete add our current level to the result array.
Return results.

Question 6 — Serialize and Deserialize Binary Tree

Serialize and Deserialize Binary Tree - LeetCode

leetcode.com

A Solution to Serialize and Deserialize Binary Tree

Solution: https://leetcode.com/problems/serialize-and-deserialize-binary-tree/discuss/74253/Easy-to-understand-Java-Solution

Our Approach:

We need two global constants for looking at null nodes and delimiter.
We are going to create 4 methods for this question. A serializer, a serializer helper (buildString), a deserializer, and a deserializer helper (buildTree).
Serialize method create a StringBuilder to store the serialized string. This StringBuilder and root of the tree is passed into the helper method. Upon the return StringBuilder is converted to string and returned.
BuildString method checks to see if the node is null, if so it adds the null node constant followed by a comma (delimiter). If not, we add our current node value followed by the comma. We also need to work our way down the subtrees so we recursively check the left and right subtrees.
Deserialize method takes in a string and converts it into a node. We create a queue to store our nodes. We add all the values from our string into our queue. This is done by taking our string and converting it into a list and utilizing the addAll() function. Finally, we need to return the tree itself, this is done by calling our helper function to generate the tree.
BuildTree method takes in a queue of strings and converts them into a tree. Before we start we check if our initial node is null. If so we return a null. If not we continue with our other nodes. We grab the next available string value from our queue and assign it to a node. We take this node and recursively build out the left and right subtrees. Finally, return the node itself which represents the tree.

Question 7 — Subtree of Another Tree

Subtree of Another Tree - LeetCode

leetcode.com

Our Approach:

We start by checking if our tree is null, if so return false as subtree couldn’t exist.
If not null, we need to run a depth-first search on on our root and subtree to check if a valid subtree can be found.
If our search fails, we need to check if the subtree exists in our left or right subtree.
For our depth-first search, we check if both root and subtree is empty, if so return true.
If only one of the two is empty we return false as trees don’t match.
If the values of the root and subtree don’t match we return false as trees aren’t equal.
If the values do end up being equal we need to check the left subtree of the root with the left subtree of the initial subtree recursively, as well as, the right subtree of the root with the right subtree of the initial subtree.