L22. Top View of Binary Tree | C++ | Java

#treeSeries #striver #placements

[takeUforward]

Please likeeee, shareeee and :) Also follow me at Insta: Striver_79

[bhargavnagacharan]

Bro thanks alot 🥺🥺🙏🙏🙏. All YouTube channels are making videos in hindi. I can't understand hindi, you are the one among very few YouTubers who provide best content in English and also u r the only one who gives both c++ and java code 🥺🥺❤️ love

[ElderMoro]

Times Complexity should be O(NlogN) because we're using map<int, int> in CPP which takes logN time to insert in the map and there are N nodes so TC will be O(NlogN).

[_PRANAYMATE]

Hey Striver, I have written down the code on my own for this problem after understanding the solution, I know it's the cake work but it gives much satisfaction that understand the logic and prepare the code than just watching the code and typing it
Thanks a lot ❤❤❤❤

[sparshsharma]

I literally saw 3-4 videos on this question but still was not able to get AC on GFG practice, in frustration, I left this question but now after watching your video, this question has become one of my favorite questions on trees. Thank you bhaiya!!
EDIT: I cut down the time complexity of inserting elements in treemap(O(logN)) to O(1) by using a Hash Map. I just stored the min value of the line in the tree and then kept on incrementing from that and kept on storing the elements.

JAVA Code:

class Pair{
int state;
Node root;

Pair(int state, Node root){
this.state = state;
this.root = root;
}
}



class Solution
{
//Function to return a list of nodes visible from the top view
//from left to right in Binary Tree.
static int traverseLevelOrder(Node root, Map<Integer, Integer> map){
Queue<Pair> queue = new LinkedList<>();
queue.offer(new Pair(0, root));

int min = Integer.MAX_VALUE;

while(!queue.isEmpty()){
Pair pair = queue.poll();
Node currNode = pair.root;
int state = pair.state;
min = Math.min(min, state);

if(!map.containsKey(state))
map.put(state, currNode.data);
if(currNode.left != null)
queue.offer(new Pair(state-1, currNode.left));
if(currNode.right != null)
queue.offer(new Pair(state+1, currNode.right));
}
return min;
}

static ArrayList<Integer> topView(Node root)
{

//This question can't be done using normal dfs beacuse there is a concept
//of levels being used in this question
Map<Integer, Integer> map = new HashMap<>();
int min = traverseLevelOrder(root, map);
ArrayList<Integer> ans = new ArrayList<>();
for(int i = min; map.containsKey(i); i++)
ans.add(map.get(i));
return ans;
}
}

[Xp-Sam]

// NOTE: In dfs there is always a possibility that some bottom nodes are visited first before the top view nodes, so we have to keep track of the levels too
void dfs(TreeNode<int>* root, map<int, pair<int, int>> &mp, int level, int column){
if(root){
if(mp.find(column) == mp.end() || mp[column].second > level)mp[column]= {root->val, level};
dfs(root->left, mp, level+1, column-1);
dfs(root->right, mp, level+1, column+1);
}
}
vector<int> getTopView(TreeNode<int> *root) {
if(root == NULL )return {};
map<int, pair<int, int> > mp;
dfs(root, mp, 0, 0);
vector<int> ans;
for(auto x : mp){

}
return ans;
}

[ashwinnema]

I solved this problem on gfg by watching this video for the first 3 minutes. Thank you for explaining question nicely

[manasambhat]

I usually never comment on the youtube videos. But this explanation was amazing. Reminds of the codeschool channel. Keep up the good work bro.

[joshrak]

I just used the same concept of vertical order traversal and just added a break statement after inserting the first element of every vertical to make sure that I always get the top-most element of every vertical basically that's the top-view

void traverse(TreeNode<int>* node, map<int, map<int, multiset<int>>> &ds, int vertical, int level){
if(node==NULL) return;



traverse(node->left, ds, vertical-1, level+1);
traverse(node->right, ds, vertical+1, level+1);
}

vector<int> getTopView(TreeNode<int> *root) {
map<int, map<int, multiset<int>>> ds;
traverse(root, ds, 0, 0);
vector<int> ans;
for(auto it:ds){
for(auto it1:it.second){
for(auto it2:it1.second){
ans.push_back(it2);
break;
}
break;
}
}
return ans;
}

[stith_pragya]

Thanks for this wonderful video....🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[KatikaneniDharaniidhar]

we can also solve this using the boundary traversal approach since the only thing that is different is that here we are not printing the leaf nodes but we are traversingg through the left and right so this would take O(h+h) for both left and right

[codeaddict]

bhaiya aap ka smjane ka trika alg level ka i loved it🙏🙏🙏

[Usurperhk]

As video starts, back to back two ads popped up,

Me : "Seh lenge thoda...."

BW. Great content on tree. Ab toh interviewer se bhi jyada janta hu 😂😂😂😂

[abhinabaprakashbora]

I think we can do it recursively by using two functions :
One for the left top view and the other for the right top view

[rawat_ji]

I was having doubt why not pre-order but at the end of video it was cleared perfectly ... thanks 😁😁 for perfect explanation

[aadityavaid]

By using unordered_map we can take two more variables (mini and maxi) to keep account of lowest vertical and highest vertical and then iterate from mini to maxi

[guptafactory]

O(N) T.C. C++ solution:

Take 2 variables l and r and initialize it to 0, 0 denoting leftmost col/line and rightmost col/line we already had.
Take queue "que" for holding all Nodes with their line/col, a stack "left" (for leftmost nodes), a queue "right" (for rightmost nodes).
Add root to the "left" and "que".

Iterate level by level (BFS) and check:
If current nodes col/line < l, update l and put node's value to "left" stack.
If current nodes col/line > r, update r and put node's value to "right" queue.

Now create a final ans vector/list.
Push all elements from "left" stack to "ans".
Then, Push all elements from "right" queue to "ans".
And, Return ans.


Code:

class Solution
{
public:
//Function to return a list of nodes visible from the top view
//from left to right in Binary Tree.
vector<int> topView(Node *root)
{
vector<int> ans;
if (root == NULL) return ans;

int l = 0, r = 0, col = 0;
queue<pair<Node*, int>> que;
stack<int> left;
queue<int> right;

que.push({root, 0});
left.push(root->data);

while (!que.empty()) {
int sz = que.size();

while (sz--) {
auto it = que.front();
que.pop();
Node* node = it.first;
col = it.second;

if (col < l) { left.push(node->data); l = col; }
if (col > r) { right.push(node->data); r = col; }

if (node->left) que.push({node->left, col - 1});
if (node->right) que.push({node->right, col + 1});
}
}

while (!left.empty()) { ans.push_back(left.top()); left.pop(); }
while (!right.empty()) { ans.push_back(right.front()); right.pop(); }

return ans;
}
};

[ashwinbalaji]

Instead of mpp.find() and then mpp[line] = node->data we can use mpp.insert({line, node->data}) because the insert func inserts the key value pair only if key is not present already. This is for c++, I am not sure about java or python 8:01

[symbol]

Wow this is the same as vertical order traversal but just taking 1 node (the first node)
So I am guessing bottom view is gonna be the same, except we take the last node on each vertical level

[mdaman]

Thanks for the free ka tree series :) great content... Bhaiya..