# Algorithm(8) Naive Tree(By input data structure)

The typical algorithm questions based on the tree structure.

This article describes several key considerations of the tree and binary search tree, we first describe the commonly techniques and thinking perspectives to solve these type of problems and then we list several specific problem and there soluations, we may put these solutions into different blogs in future.

The list of sample questions is based on this table

This part mainly contains question which provides a tree structure explicitly. The more complexed question based on decision tree or search tree can be and different context is listed in another blog. In this blog, we only list the question that provide the tree structure as the input in explicit way. This table summarize the question listed in this article.

Traverse tree Modify tree structure Tree properties
(whole tree)
Tree properties
(search path
path sum, nodes)
Serilization Search with
map optimization
94,429,987 814,669,450
701,99,108
100,572,101
110,965,872
98
111,112,129
113,437,508
124,543,235
968,501,230
297 337

### Key techniques and considerations

• (1) Classification of the tree node, instead of classifying it into the leaf or null leaf, just assume it is null or not null, or more complex form such as 968 (covered or not covered, 450 is also a good classification example, leaf node, have 1 child, have two child), 257 classifies the node to null node, leaf node and not null node.

• (2) From up to bottom, the lower level nodes need the information of the upper level nodes.

• (3) From bottom to up, the left and right child tree returns root or specific value, the upper level nodes needs the information of the lower level nodes or subtrees. Make sure which is more eaiser. Sometimes knowing the child status then compute the parent status is more easier, some times knowing parent status then process child case is more easier. 337 is a good example in this case. 98 is a good example to try both bottom to up and up to the bottom case.

• (4) Bst tree, the in order traverse (LNR) is the array with ascending values

• (5) Typical strategy to insert or delete the node, how to acquire the parent pointer for different questions (the 450 can be a complex one for this type)

• (6) The idea of calling level is important for these type of questions, For example, we may print the information of recursion level to debug the code. Besides, for the searching path, remember that the element need to be poped out after each level function call, this techniques are used in 257 and the 437.

• (7) When there is the combination of tree and the string, the key step is to map the string into the tree structure logically and we ususlly does not need an explicit tree in that case. But we may use the recursion method. It is important to remember several typical questions and what are the gaps here.

Here are some key thinking perspectives, these ideas can also be used to solving other problems, these steps are useful especially when you do not have ideas for solving current problem

• Consider the data structure adopted by the problem, from the domain specific problem to a cs algorithm problem, this step is comparatively simple for easy or medium question

• Confirm the type of problem, typically type of problem is modify, search specific results or compute optimization situation. After confirming this, we can further move to another step.

• For the problem of searching, we first need to figure out the total status and the total combinations, then we use the constrains and the techniques discussed above to narrow down these situations. For the problem of modifying, just be caring of common operations for create delete nodes, the tricks of keeping parent pointer etc.

• Other specific type of problems (such as search possible solutions) are related to tree, but not totally related, we use another blog to discuss these questions (parathesis match, work search, sudoku problem, queens problem and puzzle problem).

• (8) Sth that might be asked in the interview is actually the multi order tree or the tree with multiple children. The thought can be limited if only considering the tree with two branch. One typical question is to build a index that can find a min value in specific sub range of array. In this case, we might have multiple segment, we store the min value of each segment, the min value of whole array is must one of the these subrange, then we just find the one that is minimal in this subrange, we can even sort each level of children to accelarate the searching process. The multiple node tree can be the founudation of B tree, these question might be asked in practical interview. The start point is find an element in specific range, then move to the harder one. The complicated idea of b tree than multi-branch tree is how to make each node more balanced and split the node. The key idea behind the index is just remember the search path as it is, not the searching operation itsself. (When we search it, we build it and then we can reuse this index tree)

### Traverse tree

94. Binary Tree Inorder Traversal

This is really typical one, the inorder traversal represents the LNR traversal. The node type is divided into nullptr or not nullptr, this can be the basic framework for more complicated algorithm.

144 and 145 are similar problems, they are preorder (NLR) and postorder (LRN) traversal, respectively. 589 and 590 is the N children problem.

429. N-ary Tree Level Order Traversal

how to process the height information? There is no associated variable defination in the tree structure. This is the code that use the BFS style code based on the queue. The key idea that label the level is to remember the queue size after each level. Then at the next iteration, we just need to pop out the node in the previous level, and then the remaning elements are nodes on the current level. We do similar things and move to the next iteration step by step.

Another similar code is this one we basically need one while loop to adjust the q size and one for loop (or while loop) to monitor the number of current level.

The code can also be written in an recursive way. The general framework of recursion is easy to write, the key part is that we set the depth and insert the associated elements into the proper position. We also insert the empty array into the ans vector during the recursion process. The code of the recursive way is more clean. This is actually the dfs code, which is not the bfs code !!! The recursion call is in the dfs order.

Similar problem:

102 is also similar one, just using the level order, the code is simple when using the recursion method discussed above.

107 its input data structure is the binary tree, which is the simplified version of the 429. The 107 require the output sequence from the bottom to up. So we only need to add reverse(ans.begin(), ans.end()) before returning the ans.

104 is also similar one, just compute the maxdepth of the tree direactly.

987. Vertical Order Traversal of a Binary Tree

Using the data structure in a wise way is the key for this question. The first key of the map indicates the column, the second key indicates the row, the multiset indicates there are multiple elements in same column, row index and the elements is stored in ascending manner, and the elements can also be repeated in the set.

Compared with using a grid, using the ordered map is more simple, other soluation also use the pair as the key of the map

Similar questions:

1302, just sum up the deepest leaves, the question is, how do we know it is the deepest leaves. The idea is just using a spearate depth variable and keep the newest value, then add varaible into the sum

257 Binary Tree Paths

This question requires to print out the searching paths, one key idea is to adjust current searching path. We use a vector store the searching path, when current level of recursion finish, we then pop back the last element in the vector, by this way, we can always make sure the element in the vector is located in the current path. The similar ideas is also used in the 437, in that case, we decrease the associated path number after leaving the current recursion call each time. The search path here is based on the idea of the dfs essentially.

### Tree properties (whole tree)

Compare if two trees are same, mirror or satisfies certain constraints

100 check the same tree, we can use any type of iteration method discussed above, if there is null equal during the recursive process, return the false, otherwise, return true.

572 Subtree of Another Tree, this is the updated version for comparing if two trees are same with each other. Traverse the original tree based on NLR sequence, if the node value equals with the subroot value, executed comparision operation. Otherwise, continue check.

The above code reuse the function of 100, it still looks a little bit complicated and error prone. For the edge cases, we need to consider four situations and confirm the case that one of the child is nullptr. It also uses the idea of compare left part then compare the right part, since there is a return value of the function. For example, after deciding that the left part do not contain subtree, the right part does not contain subtree and the current root does not contains subtree, we can returns the false.

The 101 symmetric tree is also a similar question, the condition of mirror is just reverse the left and right, one case is right to left, another case is right to left, to decide if they are equal. This is similar with previous one, the difference is the traversal sequence. The origianl thought is to use LNR to traverse left and use RNL to traverse right, then compare the results. But this input [1,2,2,2,null,2] have the same results eigher for LNR and RNL. So it is not uniquely to decide if two parts are mirror of each other. Although the result is straightforward, it is not easy to provide the reuslts at the first glance.

110 check if the tree is balanced. This is a little bit special, since it introduce the idea from the bottom to up. Namely, the helper function returns some information and this information will be used by the upper level. These type of paradigm is used a lot when modify the tree structure.

965 is also a similar one, just simple checking based on the bottom to up recursion. The properties for these questions is to detect the results of the subtree first and then use the return results to decide the current results.

872 is a similar one with the simple background, the idea of code classification is good. null ptr, leaf, one child, two childern. Pay attention to the sequence of the checking and make sure all situations are considered.

98. Validate Binary Search Tree

The idea is not complicated, we make sure the left subtree is valid, the right subtree is valid, then adding the root into the tree to make the current tree is valid. There are two points, one is that we need to record the max value of the left tree to make sure current node is larger than all value in the left tree. Similar for the right subtree. Another is that the data range of the node is -2^31-1 to 2^31
This may lead to the case that the left or right node equals to the INT_MAX or INT_MIN (which is the initial status and the status when there is null node). Therefore, we need to consider the case when there is one child and two children separately to make some edge cases work. Otherwise, when the node contains INT_MAX or INT_MIN, the comparision might fail, since we could not provide a boundry value that contains these two values for integrer.

We can also set the boundry value at the long long int to simplify the code, but we need to transfer the root value into the long long type when doing the comparison:

Another idea is from the top to down, actually the code is more simpler in this case, we start from the root node and then narrow down the range of the child gradually, we set the vmin and vmax as the long int to make sure the results also correct when node equals to the INT_MIN or INT_MAX.

### Tree properties (path, path sum, nodes)

111 check the minimum depth. It also use the similar strategy. Check the min depth of the left and right part, and then return the min of the left and right value plus one. Be careful for processing the null node. Since we just return 0 direactly. When we compare the return value, this node is not accounted into the depth of the tree. For the test case such as [2,null,3,null,4,null,5,null,6], the return value is 5. When we check the min value, we do not consider the return value with the 0. Since the leaf node is the node with no children. Which should return 1 at least.

112.Path Sum, using the NLR to traverse the tree and decrease the target sum each time going to the next level. Only return true at the case where node is the leaf node and satisfies the targeted. Using the idea from the up to bottom is more natural for this one. The idea of considering things in sequence and in a complete way is important, the null node, the leaf node and the non-leaf node.

Actually, the good practice here is to consider the edge case firstly, since we can return it direactly and to not do the subsequent checking, then the remaning logic is the general case. So, the good practice for the recursion operation is to write the return entry firstly and then check the recursion part, but when we thinking it, we may consider the recursion part firstly and then the return part.

129 Sum Root to Leaf Numbers is a similar question of 112, just times 10 when visiting the leaf node when adding the new path.

113 is the updated version of the 112, it requires to memory the specific path that satisfies the requirments, it is a typical search problem (both the start and the end of the search path is clear). This idea and associated code can be the framework for many more complicated problem.

437(tricky) This is the updated version of the path sum. Compared with the previous one, the started position is not clear, the end of the path is also not clear.

special cases

solution1, use naive recursion, there might be time limit exceeded issue (did not realize the issue of the start and end point)

The following code is the optimization of the version 1, the key point is to figure out if the current node is at the start position or at the following position, that is really important, use equals to 0 to decide the condition is more simplifier than the origianl case,we need to type fewer words in this case.

This code is much more simple and refer to this blog , attention that for the first layer, the function name is the pathSum instead of the helper.

Lesson: one important idea is how to debug in recursion code: we might add the level into the print info, this can be an indicator and it can change the flattern code into the hierachy code and check the horizental and vertical. By doing this, we can find an error in our origianl code, at that time, we forget to add the condition when the path is just started. However, it is difficult to figure it out and understanding the code behaviours without the help of the debug info.

This code can be further optimized based on the 560 that computes the prefix sum. The single path in 560 changes to the multiple path on the tree for this question. Here is the optimization version for this question based on the idea of 560

The main part of visiting the node is same with the 560, main difference is that, remember to decrease specific elements from map after each call. Essentially, we need a different map for each path, but copy past map direactlly in each call is also time consuming, so we just adjust values in the map dynamically to make sure it works for different path.

508. Most Frequent Subtree Sum

The traversal part is common one, using the idea from the bottom to up, the subtree returns a particular value. The extra part is to use a map to keep track of the sum during the tree traversal process. When the max freq is updated, we clear the ans, when freq of current sum equals to the max freq, we push the current sum, when the current sum is less than freq, we do nothing. (when there is tie means there are same frequent number for the two cases)

Start and the end of the path sum is comparatively clear in this question, which decrease its level of difficulty.

124 Binary Tree Maximum Path Sum

The setting of the question is not that much straightforward and the start and end point of the path is not certained. We could confirm the general framework of the question, and use the bottom to up method approach. The tricky part is to make sure the return value and how to visit the current node.

The key thinking perspective is considering if the current node is included in the path. The maximum path can be following several options: left sum path + root, right sum path + root, left sum path + root + right sum path, or just the root itself (this situation is easy to be forgottern), since the node value can be negative, all these situations can be the maximum case.

The return part is also tricky, we just return the max value among the left side, the right side and the node itsself. Instead of returing the current possible max path sum. Since we just needs the left path or right path of the subtree to construct the new path. Anyway, the code is straightforward and the answer might need some time to come up with. Since the minpath and the return value for each recurssion call are two different variables here.

543. Diameter of Binary Tree

One similar question is the 543 which compute the diameter of the tree, these two questions use similar strategy and code framework. The 543 can be the foundataion of this question. The important point is that the helper function should not return the whole length, and it should return the max of left path or right path of the subtree. Another smart point is that they return -1 in their code when there is nullptr, which simplifies the expression from 2 layer node classification to 1 layer node classification.

687. Longest Univalue Path

The idea of this question is not diffecult, it is a little bit similar with previous several questions, the key part is consider every situation clearly

For the version1, we calssify the node by null, leave node, one child, two children case. Then in the two children case, we further consider the relationship between the root node and the child node.

For the case2, we kind of merge the situation where there is one children and two
children case. Since when wen want to decide the situation of two children, we need to first decide the case when there is one children.

236(235). Lowest Common Ancestor of a Binary Tree

The naive solution is to use the idea based on the 257 which can remember the path of the tree traverse based on the dfs. When the node comes to the p, remember the path. When the node comdes to the q, remember the path. Then compare two path to find the last one that is same with each other. This node is the LCA node. For this solution, remember that we can not guarantee the sequence to find the p or q, it is possible to find p first or find the q first.

This is another solution for this question. It use the idea that combines both top to down and bottom to up, it uses both current value and the value of lchild or rchild to decide the least common node in the tree. This method can avoid some unnecessary recursion operations.

It can decrease some search path depending the position of p and q. Consider the three node, current node (c), p and q. There are several possibilities about their positions:

a)p and q are not at the subtree of the c, return null in this case.
b)p and q are at the left subtree and right subtree respectively, return c in this case.
c)p and q are at one subtree of the c.

There are two further situations for the case c), the first one is that the c equals to p or q, return the c direactly in this case. Another situation is that the c not equals to p or q, in this case, return the lchild or rchild that is not null.

Here is a good explanation for this question (https://www.youtube.com/watch?v=KobQcxdaZKY)

968. Binary Tree Cameras

It looks like a dp problem, since for each step, we can choose place camera or not

There is one answer looks a little bit complicated, but we considered things in a systamaticall way. Nameyly, null node, one child case and two children case. The status transfer between the two levels of the tree is important for solving the problem.

One tricky part is that when both left and right is the no camera but covered status, we have two options for the current node, either put camera here or weight for its parent. It looks that the dp approach is more general soluation. By analyzing this problem we can find that iftop is true, we prefer to put camera, other wise, we wait for the upper level node to put the camera.

I still did not figure out the how to compress the one child case, some code returns the camera monitored status when the node is null.

After simplifying the code and assume the null node is the dummy node with the status NCM, we can get this simple code, although the code is simple, but the logical process to create this code is not simple, we need to consider all 3*3 possibilities and compress them into the simplified form as follows:

979. Distribute Coins in Binary Tree

The code is easy, but the thinking perspective is important and it is not easy to get that point. We use the bottom to up method during the search, the return value for each layer represents how many coins is needed to make the current node and its subtree to satisfy the constraints (this idea is the key for solving the problem). For the simple case, such as the leaf node, the return value of the subtree is 0, they do not need extra coin move. For the case [3,0,0], at the node with value of 3, the return value of the left and right subtree is -1, we need move 1 conin to them. Then in order to make the node with value 3 become case that satisfies the requirements, we need to move 3-1 = 2. Adding this value with two return results, they become 2-1-1=0, so we do not need extra move. When we compute the move count, we use the abs value, no matter we move from current node or move to the current node, the move count through the edge should add one.

530 and 700 are similar questions that use the bst tree. 501 is also a similar one, the idea of updating the most frequent elements and associated length is inspiring. We consider three exclusive cases when checking the current node.

One tricky case is sth like [1,null, 2,2] do not update the recorded value based on the principle such as if current elem eqauls to the previous one. Since we do not know if there are more subsequent elements. For each step, we assume it is the last element.

When there is [1,null, 2] the ans vector contains 1 and 2, then move to the next, update the count, then clear the ans, then push 2 again. The key point here is we actually push the element 2 into the vector twice.

501. Find Mode in Binary Search Tree

230. Kth Smallest Element in a BST

This is the updated version of the 700, the LNR traverse is important, in BST, the LNR is the sorted ascending sequence, therefore, we can confirm the position of the kth smallest elements conveniently by gradually decreasing its value.

### Modifing tree structure

814. Binary Tree Pruning

Pruning the subtree with a particular properties. The common strategy is from bottom to up and let every subtree satisfies the requirments firstly. Be careful of the condition. If current node contains 0, and one of the child exist, it means that one of the subtree contains the 1, the current node and subtree satisfies the condition and should not be removed. The idea from bottom to up to reconstruct the whole tree is crutial for the problem that need to modify the tree structure.

More complicated trim operation, we need to adjust tree structure

The key strategy here is to consider the type of the node during the removal operation, if the removed node is leaf node or the node with one child or the node with two childern, etc. The code is more clear if considering things in this way.

669. Trim a Binary Search Tree

The operation is simple, just delete a node and adjust the tree structure. Be careful for the case discussion when we detected that the node should be removed.

Actually, this code can be further improved and we can notice that the case when there are two children if actaully not exist.

For example, if the current node value is c and it does not blongs to the [L,R], if c<L, all the nodes in left of the c < c < L, so all of these nodes should be removed till the current step. Similarly, when the c>R, all the right side nodes of the c > c > R, so the right side subtree should be removed before hand. This fact shows that there only exist two cases for the current recursion step, either c is the leaf node or have one side subtree.

1325 is a similar question, the constrains of removed node is more simple in this question.

450. Delete Node in a BST

The code framework and main considerations for this problem are similar with the previous one. Reuse the existing operation to deleted the selected node for the two children case is a smart point.

701. Insert into a Binary Search Tree

Using the bottom to up method and return the root of the sub tree after the modification.

99. Recover Binary Search Tree

This question utilizes two facts. The first is that when there is ascending sequence, there is LNR operation. Another fact is that in the ascending sequence, if we change two numbers, by checking all the elements, if there is one situation with a1>a2, we know that we switch the adjacent numbers. When there are two these cases, we can make sure that these two numbers are not at the adjacent positions.

If we do not use the fact of LNR and ascending sequence, there is C(n,2) possibilities for two numbers, this is a huge searching space.

108. Convert Sorted Array to Binary Search Tree

This is bascially the process of reconstructing the bst tree. The bst property simplifies the code a lot. More complex one is the case that decerilize from a random case, check the 297.

### Tree + others

This type of questions use both the techniques used in tree and array (maybe map) to solve the problem. The key step here is to make sure what is the decision tree. In this blog, we only show some typical questions, such as serilization and using the map to do the accelaration. More general question that use the decision tree to do the search can be found in another article.

#### tree+string (serilization)

The input of the function is a string in this type of question. And it may potentially use the tree structure to derive the property of the tree structure. The difficult part is how to map the string structure into the tree structure. That is way these questions looks tricky firstly, we should first try to transform it into a tree type problem logically.

297 Serialize and Deserialize Binary Tree

The idea of this question is not complecated, but it is really error-prone. We use the layered traversal here based on the queue, be careful about the condition that when there is the mix of the nullptr node and the actual solide node. This is a little bit different with the level order question such as 429, since the null node also need to be considered if current level contains both empty and solid node

The similar one is the 449, we can also use the similar level traversal techniques. Is there more efficient techniques for the bst structure?

### Tire tree or dict tree for accelaration

The 212 is a good exmaple, we need to do the similar search operations for multiple times, it can save time if we first trasfer the original structure into a tired tree for accelarating searching process to avoid the redouantant searching. The idea is to extract the common part of the tree. Look at more details for the details in the search part.

#### tree+map or dp (using map to optimize the code)

Some complex path sum questions may use the map, such as the 437. The main idead that uses the map is to improve the performance of the searching.

337. House Robber III

This one is inspiring. There is some intersection between the traditional tree based strategy such as top to bottom or bottom to up with the thinking perspective of the dp.

For example, this is the code from the top to bottom. We make sure the status of the start node (parent node) and then considering the status of the child node.

and this is the code from the bottom to up. We make sure the status of the child node and then refer to the status of the parent node.

If we consider the issue from the status transfer, the parent node and the child node mainatins a kind of relationship (depending on the context of the question), the status table is listed as follows from the child to the parent

L R C
R NR NR
R R NR
NR NR R/NR
NR R NR

we could check the parent firstly or child firstly, there are two different programming paradigm. For the first version, we use the strategy from start to the end. For the second case, we fix the status of the leaf node firstly, then derive it from the bottom to the top. Even for previous questions that search the properties of the tree, we also use the similar ideas. These questions only have one variable and the status is also comparatively simple.

Inspired by the dp solution of the 337, we can write another dp solution of the 968. Binary Tree Cameras:

This code is easy to understand if we list the status transfer between children and the parent:

L——R——C
CM CM CM/NCM/NCNM
CM NCM CM/NCM/NCNM
CM NCNM CM
NCM CM CM/NCM/NCNM
NCM NCM CM/NCNM
NCM NCNM CM
NCNM CM CM
NCNM NCM CM
NCNM NCNM CM

The tricky point is the status when there is nullptr, at that case, we should assume the node status is the NCM. For the origianl solution, it assume that when there is CM or NCM, it is always prefered to postpone the camera except the current node is the top layer, so we can guarantee the status of the tree by this analysis. But the dp solution is a more general case.