Approaches To Problem Solving #17(Tree | DFS)
Problem: Given a binary tree, return the longest path that alternates, going down from one child to the other child. For example, it may alternate between right child, left child, right child, etc. Or left child, right child, left child, etc, going down.
Let us consider an example to understand the problem better,
We can explain the above example as follows,
We will try to approach this problem, by keeping in mind what information does each node require. It is intuitive to think of having two pieces of information to be returned to each node, one from its left child and other from its right child. What information are we talking about? Let us think of this information in terms of a pair.
The first entry of this pair tells us what the contribution of the current node is if we were to move to the right child and similarly, the second entry of this pair should tell us about the contribution if we were to go left, next.
Approach: We start traversing the tree from the root node using Depth First Search. We return a pair from all the nodes as stated above. For the above given example we can visualise our given method as follows,
If we look at the picture above closely, we will be able to figure out how the return values have been generated for each node. Again, for each node, the pair of values getting returned tell us about the longest alternating path that we can take starting from this node. Why did we use the concept of pairs here? Well, the reason behind considering pairs here is that, we need to find out the best solution for the given node if we move to either the left child or the right child, next.
We use these values getting returned from children nodes to construct the answer for the current node.
Mathematically,
answer[curr->left] = dfs(curr->left),
answer[curr->right] = dfs(curr->right),
answer[curr] = {1 + answer[curr->right].second, 1 + answer[curr->left].first}
where “curr” denotes the current node being explored and “answer” is an array of pairs holding the solutions for all the nodes.
Finding the maximum out of the first and second pair values of all the nodes would lead us to the final solution.
We need to keep in mind that a NULL node returns {0, 0}
The time complexity for this solution is O(N), where “N” is the total number of nodes in the tree.
In our next article, one of the problems that we are going to discuss is given below,
Problem: Given a 2-D list of integers containing 1s and 0s. Return a 2-D matrix representing the Manhattan distance of the current cell from the nearest 0 cell. It can be assumed that at least one 0 exists in the matrix.
We hope that this article would have helped at least some of you in developing the skill of breaking the problem down and approaching it step by step. Feel free to explore the concepts of Tree and DFS further!
We will try to keep you updated with the problems and their discussions as we come across them. Feel free to share your thoughts on the same.
For hugs and bugs, please comment down below. Till then.. Happy Coding!
This is the 17th article of the “Approaches To Problem Solving” series.
More such posts can be found at :-
