L23. Bottom View of Binary Tree | C++ | Java

Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL, AI doubt support and many other features that will help you to stay focussed inside one platform under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing.

[takeUforward]

Hi, hope you are well.


Find DSA, LLD, OOPs, Core Subjects, 1000+ Premium Questions company wise, Aptitude, SQL and many other time saving features under one affordable subscription. Have a hassle free one stop solution for up-skilling and preparing yourself.

[adityabalodi]

In case the question asks to store the left value instead of right when both nodes are at same place, just do the level order traversal from right to left.

[bharathkumar]

// code for recrsive approach, just keep track of row number.
//Structur of map: colum_no={data, rownumber}
//if row number is larger than previous stored data, then replace.

void f(BinaryTreeNode<int> * root, int row, int col, map<int, pair<int, int>> &mp){
if(root==0)return;



if(row>=mp[col].second)
mp[col]={root->data, row};



f(root->left, row+1, col-1, mp);
f(root->right, row+1, col+1, mp);

}

[chandrachurmukherjeejucse]

Understood.
Recursive code:
Modification: keep track of ht along with line and check if there is a element present on the line or not. If not then insert that, otherwise check if ht is greater than or equal to the previous or not. We have to include == becasue we will always traverse the left part first and then second so if in the right subtree there is a node at the same level then that will be the rightest one.


void inorder(BinaryTreeNode<int>* root, int x, int y, map<int, pair<int, int>> &bottomView) {
if(root == NULL) return;

if(bottomView.find(x) == bottomView.end() ||
y >= bottomView[x].first) {
bottomView[x].first = y;
bottomView[x].second = root -> data;
}

inorder(root -> left, x - 1, y + 1, bottomView);
inorder(root -> right, x + 1, y + 1, bottomView);
}

vector<int> * root){
vector<int> res;
if(root == NULL) return res;

// x y data
map<int, pair<int, int>> bottomView;

inorder(root, 0, 0, bottomView);

for(auto p: bottomView) {

}
return res;
}

[RitiKumari]

I am very much happy and impressed by the fact at last you let us know why one shouldn't use recursion . Awesome explaination Must Say !!!

[VishalGupta-xwrp]

TC will be O(N) for BFS Traversal * O(LogN) as we are using Map.

So overall O(N*LogN)
Yeah for space complexity you can say overall it will be O(N)

[lakshmand]

In top view of the tree we check before adding to the map if there is an existing node from that particular line number, simply remove that checking condition that's all your code for bottom view is done :)

[nitishbyahut]

done before you explaining... that's the level of ur teaching... u make us think nd do it ourselves.... Thanks a lot #saviour

[dushyantsinghkhichi]

Thanks Striver Bhaiya for Uploading such high quality content for free on Youtube it feels more than any paid content.

[bhaveshkumar]

Best DSA content. Miles and leagues ahead of other channels! 🙌🙌🙌

[aniketsaxena]

As soon as you said vertical order traversal, I closed the tab and solved the question. And I got to learn about vertical order traversal, 🤣

[akashjha]

dhanybad bhaiya aapke wajah se hum ab tree pe chadna start kar diya hai thoda thoda

[ammanchhetri]

the change we can do is ig...we can carry another parameter as depth...and we will create a map like map<int, pair<int, TreeNode*>> ...where the int inside the pair is the depth...so we only update the vertical if the current depth is greater than the stored depth....maybe this should work

[charlesbabbage]

Truly AMAZING explanation. You're such a KING!

[aryanjoshi]

we can also do the question with the help of a stack
Map<Integer, Integer> mpp = new TreeMap<>();
Stack<Tuple> stack = new Stack<>();
Queue<Tuple> container = new LinkedList<>();
ArrayList<Integer> ans = new ArrayList<>();
container.offer(new Tuple(root, 0));
while(!container.isEmpty()){
Tuple temp = container.poll();
Node node = temp.node;
int line = temp.line;
stack.push(temp);
if(node.left != null){
container.offer(new Tuple(node.left, line - 1));
}
if(node.right != null){
container.offer(new Tuple(node.right, line+1));
}
}

while(!stack.isEmpty()){
Tuple temp = stack.pop();
Node node = temp.node;
int line = temp.line;
if(!mpp.containsKey(line)){
mpp.put(line, node.data);
}
}

for(Map.Entry<Integer, Integer> entry : mpp.entrySet()){
ans.add(entry.getValue());
}

return ans;

[abhishek_]

This explanation is astounding! The explanation of why recursive traversal is ineffective in this situation struck a deep chord.

[satyamsingh_]

Shouldn't the worst case time complexity be O(n Logn) in case of skewed tree, because of map/TreeMap?

[algoman]

I was just doing by recursion without thinking of the last example which u have shown ..thank you so much ❤️

[rishabhgupta]

Using recursion can also be solved
void preorder(Node *root, int vlevel, int hlevel, map<int, pair<int, int>> &m)
{
if (root == 0)
return;
if (m.find(vlevel) == m.end() || m[vlevel].first <= hlevel)
m[vlevel] = {hlevel, root->data};

preorder(root->left, vlevel - 1, hlevel + 1, m);
preorder(root->right, vlevel + 1, hlevel + 1, m);
}
vector<int> bottomView(Node *root)
{
map<int, pair<int, int>> m;

preorder(root, 0, 0, m);

vector<int> res;

for (auto ele : m)
{

}

return res;
}

[AdityaMaurya-dwod]

Being able to solve these question on my own coz of your previous explanations. Thankyou Striver!!!