What is the mistake in my code

#1
#2

hello @gaurav19063
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.

#3

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 << " "; 
}

}

#4

please tell me am i making tree correctly?

#5

But in the given test case they consider right most node if at a same horizontal and vertical distance

#6

can u please share the screenshot

#7

Screenshot from 2020-06-18 14-35-34
Screenshot from 2020-06-18 14-35-341920×1080 183 KB

#8

yeah u r right .
here they are considering rightmost one.

the issue is with ur build tree,
if u see ur for loop , it will stop when d will become -1.

but it is possible that there r input even after that.
for example
1 -1 2

simple idea will be to do level order traversal and build tree

#9

then when will i stop the loop, should i keep track of count of -1’s

#10

if u want really want to use that array approach.
then it is too easy , u really no need to build tree .

simply read level order and put then in array.
now tree is ready ( did u remebr how we use to implement heap using array).
root is ur index 0.
for any index i .
left child -> 2i+1
right child -> 2i+2

if any of the value is -1 then that means that node is null

#11

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.