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

12 min readJul 20, 2022

Please be sure to check the last week’s article on trees. This will be a continuation of the remainder of those questions. Please refer to the previous article for some concepts not described in this section

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

Moving on to what I believe to be the most important chapter, I will break it down into 2 sections. For this section, I…

medium.com

Question 8 — Construct Binary Tree from PreOrder and InOrder Traversal

Maximum Depth of Binary Tree - LeetCode

leetcode.com

A solution to Maximum Depth of Binary Tree

To best solve this question we need to understand the relationship between inOrder and preOrder sort. I’m going to attach the picture from leetcode solution below because I believe it does a great job of visualizing the problem which makes the recursion much easier to understand.

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/

Our Approach:

We create a helper function to construct a tree utilizing the two traversals. For this method, we need many arguments to pass information down recursively. The following are necessary arguments: starting index of preOrder, starting index of inOrder, the end index of preOrder, the array of preOrder sort, and the array of inOrder sort.
To start off we call our helper method both with 0 start indexes and the last element as the ending index with the two arrays.
Inside our method, we check if the starting index of the preOrder sort surpasses the length of the preOrder array itself, as well as if the starting index of the inOrder index passes the end index. If any of these occur this is not a valid traversal, thus, we return indicating the end of the leaf.
To start we create a new root for our tree. This is the starting index to our preOrder traversal.
Next, we need to find the location of our root value in our inOrder traversal. Since the inOrder array is not sorted we linearly search throughout the array until we find the matching value.
The following is the tricky part that takes quite a while to understand I will try to do my best in explaining why we passed each parameter. After grabbing the root need left and right subtrees.
For our left subtree we recursively call the helper function. We move our preOrder index forward by one as we already used the first index of the array, we hold our inOrder start as before, our inOrder ending index now has to be one less than the index we found when searching for the root. The best way to visualize this is the left side of the array from the root in the inOrder array representing the sour left side tree. And the right side represents the right subtree.
For our right subTree once again we make the recursive call to the helper. Our initial index is a little trickier. We get our current start and add the starting index of the inOrder array. From this, we subtract the start of the inOrder array and add one. We need to skip all the elements on the left side of the tree. To do this we take the index point of our root and subtract it from the starting index of the inOrder. This way we have found the number of elements in the right subtree. Now to make sure we acquire the next available element, we push our index forward by one. The remainder of the parameters are very straightforward, we need the next element in our inOrder array after the root. We grab the index of the root in our inOrder array and add one to skip that element; this now represents the starting point of our inOrder element. The remainder of the parameters remain.

Question 9 — Validate Binary Search Tree

Validate Binary Search Tree - LeetCode

leetcode.com

A Solution to Validate Binary Search Tree

What makes a binary search tree? One of the key attributes is the fact that it can be traversed with an inOrder traversal and give us an ordered list. Using this attribute we can check if a BST is valid or not.

Our Approach:

Declare a global variable to keep track of the last checked node.
Create a helper function to see if the binary search tree is valid.
This function is done by creating an order sort and checking if it’s valid. This is because an in-order sort on a binary search tree should result in sorted order.
For our method, we check if the root is empty. If so a tree would be deemed valid, thus, return true.
We proceed with the left subtree and recursively check if it’s a valid tree, if not return false. If true, continue with the method.
We compare our root to the last value. Within the order, the sort root should be greater than the previous. Therefore, if smaller we return false. We check if the last is not null, this is necessary for our first iteration where the previous variable has not been changed.
If we find last to be less than root that means our in-order search thus far is in the correct direction. We update our last variable to reflect our root value as it has passed our search thus far.
Continuing with our in the order sort, we check the right subtree to see if it is valid. If our right subtree is valid, we continue with our method and return true as the final statement.

Question 10 — Kth Smallest Element in a BST

Kth Smallest Element in a BST - LeetCode

leetcode.com

A Solution to Kth Smallest Element in a BST

Like before we know an inOrder traversal gives us an ordered list. So utilizing this technique we can just make our way through the array and keep tracking each smallest element we find until we reached the kth smallest element.

Our Approach:

We create a global variable to track how many remaining values there are to get to the kth element.
We set our remaining variable to k itself and call our helper method to run an in-order sort.
In our helper method, we take in the root of a tree and run an in-order sort. To start this sort we check if the root is null, if so we return a negative one so we can go back one on the kth elements when we reach a node null.
For in order traversal we need to visit the left subtree to start. For this, we recursively call the left subtree.
We check if our answer isn’t a negative to make sure no empty trees aren’t returned. We return our answer from this point.
If haven’t found our kth element yet we move forward to another element. This is done by decrementing the remaining variable.
If our remaining is zero it means we are at our kth smallest element. We return the value of our root.
If our remaining isn’t zero we must continue with our in order search, thus to continue with an in-order sort we examine the right subtree.

Question 11 — Lowest Common Ancestor of BST

Lowest Common Ancestor of a Binary Search Tree - LeetCode

leetcode.com

A Solution to Lowest Common Ancestor Of BST

For this question understanding how a binary search tree is structured allows us to traverse the tree and look for the position at where the lowest common ancestor exists. We have 2 possible scenarios to account for: if the root is greater than both p and q, or if the root is less than both p and q. Once we understand which one of these scenarios we are in, we can recursively traverse our tree.

Our Approach:

There are two conditions we consider for this question to find the lowest common ancestor. In the first one, we check if the root is greater than the p and q values lowest common ancestor must be in the left subtree. So we recursively call the left subtree of the root.
If root is less than p and q, our lowest common ancestor is in the right subtree.
Finally, if both these statements fail, it means it’s between p and q. If this is the case we can return the root itself.

Question 12 — Implement Trie (Prefix Tree)

Implement Trie (Prefix Tree) - LeetCode

leetcode.com

LeetCode Solution: https://leetcode.com/problems/implement-trie-prefix-tree/discuss/1509492/Java-or-Fast-or-Easy

This is a question of purely understanding the data structure of trie. I would do some research to get familiar with the data structure itself and how it works before attempting this problem. I have attached a link below for a good explanation of the data structure.

https://drstearns.github.io/tutorials/trie/

Our Approach:

We declare the data structure for a node. Each node has an array of nodes that its parents. We also need some way to show if we are at the end of a word. For this, we can utilize a boolean flag to show us if a node is the last one or not. Finally, we create a constructor to initialize each node. For this, we set the children the length of the English alphabet at 26 letters, and the end flag to false.
Next is our constructor for Trie, this is done simply by creating a root node. For this, we declare a global root variable and create a new node utilizing it.
Next, we need a method to insert words into our trie. We start this by creating a current node that points to our root variable. We iterate through the word we are inserting, on each iteration we cache our character. If we don’t have the character in our list of children we create a new node for this character. Next, we need to have our pointer move from root to point at the next character. So now, the current pointer points to the child that was most recently inserted. Finally, when we reach the end of a word we set our end flag to true to indicate the ending of a word.
Our search method is very similar to the insert method we just developed. When we search we return if a word was found or wasn’t. This is done by checking if we have reached the end of a word by the end of our search. So, like before we start iterating through our word till we reach the end. If we run across any characters not in the word at any point we return false.
Finally, we need to develop a start with the period for searching for prefixes. This method works the same way as the search method we previously created. However, unlike the search algorithm, we don’t need to check if we are at the end of a word since we are only looking for a prefix.

Question 13 — Add and Search Word

Design Add and Search Words Data Structure - LeetCode

leetcode.com

Leetcode Inspiration: https://leetcode.com/problems/design-add-and-search-words-data-structure/discuss/59718/Easy-to-understand-Java-solution-using-Trie-and-Recursion-with-explanatio

Like before this question is a trie problem so we will use a similar approach to the previous question.

Our Approach:

We declare the data structure for a trie node. Each node has an array of nodes that its parents. We also need some way to show if we are at the end of a word. For this, we can utilize a boolean flag to show us if a node is the last one or not. Finally, we create a constructor to initialize each node. For this, we set the children the length of the English alphabet at 26 letters, and the end flag to false.
Create a global root trie node
Next, we need a method to add words to our trie. We start this by creating a current node points to our root variable. We iterate through the word we are inserting, on each iteration we cache our character. If we don’t have the character in our list of children we create a new node for this character. Next, we need to have our pointer move from root to point at the next character. So now, the current pointer points to the child that was most recently inserted. Finally, when we reach the end of a word we set our end flag to true to indicate the ending of a word.
Our search method is very similar to the insert method we just developed. When we search we return if a word was found or wasn’t. This is done by checking if we have reached the end of a word by the end of our search. So, like before we start iterating through our word till we reach the end. If we run across any characters not in the word at any point we return false.

Question 14 — Word Search II

Word Search II - LeetCode

leetcode.com

LeetCode Solution Inspiration: https://leetcode.com/problems/word-search-ii/discuss/59780/Java-15ms-Easiest-Solution-(100.00)

For our final problem, this is going to be a combination of a few techniques we have used in previous questions. First, we need to use try to store the words we have looked through. As well as this Trie we create depth-first search to find all the possible words given a starting position.

Our Approach:

Like before we create our trie node. We need a map for the children as well as a string to store the final word so we can add them to our results as we visit them.
Next, we look at our main method of finding words. We start by declaring our return variable to store the list of strings we will return upon the completion of our method.
We continue our method by building our trie which will allow us to search words. The trie is built utilizing a helper method. We iterate through each word available and with each iteration we create a pointer starting at the root. After this, we iterate the characters in the word itself. We check if the children of the trie node include the letter we are currently on. If not, we create a new node to hold this new child and assign it to the children. We proceed with this by moving the children’s node to the now latest child. As we finish each iteration we assign the word to each node in the trie. Finally, the root is returned as trie is now built.
After we have finished creating our trie, we traverse our 2d board. In each cell, we run a depth-first search to find all the possible words. For this, we call a helper function to run the DFS algorithm to each cell that we visit.
Our DFS algorithm starts off by caching the current cell value so it can be used throughout our method without having to call the cell over and over.
We proceed by checking if the character is found in our list of children. If not, we are just going to return at this point in time and we are done with the DFS. If found, move the pointer to the child node.
We check if the updated pointer is a word. If it is, we add the word to our result list and follow it up by setting the word to null so duplications won’t occur in our list. After, this we acknowledge a cell has been visited so we change it to a character that isn’t found in words. In our example, we utilize the ‘#” character.
After we have found the words, we run our depth first search itself. We have to search all 4 directions when we are looking at a 2d matrix. So using if statements we search up, down, left, and right. These are all going to be recursive calls so DFS runs on each cell, and cells get marked as visited.