Approaches To Problem Solving #19 (BFS | Tree)
Problem : Given a binary tree root, return the top view of the tree, sorted left to right.
Let us consider an example to understand what we are required to do.
We can explain the above example as follows,
In most of the problems related to the concept of Trees, thinking on the lines of picking the best way to traverse the tree, often makes it easier to find a solution.
Since we are concerned with showing the top view of the tree in some order, we can safely assume that the nodes closer to the root have to be given more priority compared to the ones below them, if they meet the right criteria.
This gives us a hint that we should try to approach this problem with keeping Level Order Traversal in our minds.
Approach : If we provide each node with some reference id, we can distinguish between the nodes on the basis of how left do they appear in the given tree. This can be done if we sequentially provide the reference ids from left to right on each level independent of the other levels.
Since we are providing ids to the nodes closer to the root node first, we perform a Breadth First Search starting from the root node.
Assigning of the reference ids can be done as; if the current node has an id ‘i’, its left child gets the id ‘i — 1’ and its right child gets the id ‘i + 1’. The first time a node gets some unique id, the node is pushed to our answer array.
Keeping in mind that we have to return our answer array sorted in the form of the smallest reference id first, we sort the answer array on the basis of the reference id. We have our solution !!
The time complexity for this solution is O(N + N * logN), where ’N’ is the 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 two strings S and T. Consider taking a non-empty subsequence from S, a non-empty subsequence from T, and then concatenating the first subsequence with the second. Return the longest possible palindrome that can be constructed.
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 BFS and Trees 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 19th article of the “Approaches To Problem Solving” series.
More such posts can be found at :-
