Tree bottom view

#1

one test case not pass

#2

hello @ajayrajsingh_817
bottom view depends on two things horizontal distance and level.
but u r considering only one of them.
this is the approach using map.
image

void printBottomViewUtil(Node * root, int curr, int hd, map <int, pair <int, int>> & m)

{
// Base case
if (root == NULL)
return;

// If node for a particular  
// horizontal distance is not 
// present, add to the map. 
if (m.find(hd) == m.end())  
{ 
    m[hd] = make_pair(root -> data, curr); 
}  
// Compare height for already  
// present node at similar horizontal 
// distance 
else 
{ 
    pair < int, int > p = m[hd]; 
    if (p.second <= curr) 
    { 
        m[hd].second = curr; 
        m[hd].first = root -> data; 
    } 
} 
  
// Recur for left subtree 
printBottomViewUtil(root -> left, curr + 1, hd - 1, m); 
  
// Recur for right subtree 
printBottomViewUtil(root -> right, curr + 1, hd + 1, m);

}

void printBottomView(Node * root)
{

// Map to store Horizontal Distance, 
// Height and Data. 
map < int, pair < int, int > > m; 
  
printBottomViewUtil(root, 0, 0, m); 
  
 // Prints the values stored by printBottomViewUtil() 
map < int, pair < int, int > > ::iterator it; 
for (it = m.begin(); it != m.end(); ++it) 
{ 
    pair < int, int > p = it -> second; 
    cout << p.first << " "; 
}

}

#3

didn’t get what you are saying

#4

why are you using level ???
i have done top view with same approach and it passes all my test cases
n here only one test case not passes rest all passes
what is the use of level here

#5

how we determine a node is bottom node or not ?
we can can determine with the help of level/depth right?

horizonatal distance is not sufficient to determine bottom most nodes ,
because there can be so many nodes with same horizonal distance, and among all those node we have to print only that node whose depth/ level is maximum.
that is the why i m considering level/depth as well

#6

i am updating it with same horizontal distance and at last we get bottom node

#7

can you please check my code

#8

save ur code here->


and share the link

#9
#10

see your code is correct.
but it is failing because if there is more than one node that at bottom and having same horizonal distance then in that case u should consider the left most one(to pass the test cases) but u r considering right most

1
/ \
2 3
\ /
4 5
among 4 and 5 u code will print 5, but in test case they have considerd 4.

to handle such cases u should consider level as well.

#11

by handling level it passes all test cases???

#12

yeah it will pass . . . . .

#13

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.