TREE BOTTOM VIEW

#1

In this question, how can we make a level order tree?

#2

hello @CODER_JATIN
construct ur tree by doing level order traversal.
read data , build a node and then read data for left subtree (if it is -1 then it is null otherwise build a node and push it in queue)
then read data for right subtree (if it is -1 then it is null otherwise build a node and push it in queue)

refer this->
image

#3

or bhaiya “PRINT BST KEYS RANGE” walw question mai , If input we give is 5 3 2 1 0 4 8 7 6 9 , and range is (1,8) then what should be the output?

#4

one aur 8 ke bich me jitne bhi keys has wo saare output me aa janyenge

#5

1 or 8 ke beech mai saare elements including branches?

#6

branches? jin jin nodejs ki value 1 se 8 ke bich me ha wo sab output me hona chaiye

#7

thik hai bhaiya okay!!!

#8

bhaiya ,bottom print krane ke liye kese approach krenge?

#9

bhaiya ,bottom print krane ke liye kese approach krenge?

#10

The idea is to create an empty map where each key represents the relative horizontal distance of the node from the root node and value in the map maintains a pair containing node’s value and its level number. Then we do a pre-order traversal of the tree and if current level of a node is more than or equal to maximum level seen so far for the same horizontal distance as current node’s or current horizontal distance is seen for the first time, we update the value and the level for current horizontal distance in the map. For each node, we recurse for its left subtree by decreasing horizontal distance and increasing level by 1 and recurse for right subtree by increasing both level and horizontal distance by 1.


void bottomViewHelper(node *root, int level, int dist, map<int, pair<int, int> > &mp) {
    if(root == NULL) {
        return;
    }
    if(mp.find(dist) == mp.end() or level>=mp[dist].second) {
        mp[dist] = {root->data, level};
    }
    bottomViewHelper(root->left, level+1, dist-1, mp);
    bottomViewHelper(root->right, level+1, dist+1, mp);
}
void bottomView(node *root)
{
   map<int, pair<int, int> >mp;
   bottomViewHelper(root, 0, 0, mp);
   for(auto val:mp){
       cout<<val.second.first<<" ";
   }
}
#11

Bhaiya , Map to abhi pdha hi ni ?

#12

stl map padh lo, 10 - 20 min mein aa jayega

#13

pair<> ki tarah hi hota hai naa?

#14

ek baar dekh lo, samajh aa jayega

#15

https://ide.codingblocks.com/s/437211 , bhaiya check karna code kya dikkat hai?

#16

saara issue map se related hi hai,
tum pointer ko as key istemal nahi kar sakate.

aur find function iterator return karta hai
to tum usko . (dot) operator ki help se access nahi kar sakte arrow operator lagega.

iska method 1 dekho ->link

isme jaise map use kiya hai, waise use karo.
node * ko key mat banao

#17

jese maanlo map mai key value hoti hai , to map[key] will be equal to value hogi?

#18

ha . … . . . . . … . … … …

#19

https://ide.codingblocks.com/s/437282 , bhaiya dekhna code chal to gya lekin ,jab ham iterate karke map ko print kara rahe hai to usse pehle sort bhi to karna pdega map ko ?

#20

nahi map by default key ke according sort kar deta hai