Tree bottom view doubt

#1

How to take input in this question.
SAMPLE INPUT:
1 2 3 4 5 6 -1 -1 -1 -1 -1 -1 -1
what should be the algo for this?

#2

@i_m_vishesh hi vishesh this input can be achieve by level wise you have to take buildtree with the help of queue prateek bhaiya taught us tree buildlevel wise go and watch github repo where prateek bhaiya build a function buildtreelevelwise

#3

OK thanks!!!
got it.

#4

@jaiskid @ashishnagpal2498
for the above input tree formed is
_______1
___2 _______3
_4 ____5,6
OUTPUT GIVEN : 4 2 6 3
why 5 is not there in the output with 6
shouldn’t it be 4 2 5 6 3???

#6

Hi Vishesh , the reason why 5 is not in output is because 1 5 6 are on same level as viewed from bottom , and so 6 is the last node to enter in that level , hence 6 is viewed .
The tree is basically like -
_______1
___2 _______3
_4 ____5 ___
______6 _______

1 Like
#7

@ashishnagpal2498
https://ide.codingblocks.com/s/63132
getting wrong answer in one test case. I hv tried many corner cases but not getting what is wrong.

#8

Hi , Vishesh , I just checked your code ,
For this given input set - 1 2 3 -1 4 5 -1 -1 -1 -1
The output should be 2 5 3 , but your code gives output as - 2 1 3 .
Instead of checking the if condition after the recursion do it before the recursive call as you have to overwrite new value in the level , with the previous value.
https://ide.codingblocks.com/s/63437

#9

@ashishnagpal2498 actually by mistake i shared the code link of tree top view.
i have checked the if condition before traversing only.
here is the correct link: https://ide.codingblocks.com/s/63441
and one test case is giving wrong answer for this.

#10

Hi Vishesh, consider the following test case:
Input:
20 8 22 5 3 4 25 -1 -1 10 14 -1 -1 -1 -1 -1 -1 -1 -1
Expected Output:
5 10 4 14 25
Your code’s output:
5 10 4 22 25
The right tree is traversed after the whole left tree is traversed . That is why the the value 14 is overwritten by 22 .
Kindly refer to this code - I have made a slight change in your code , by storing both node and level . https://ide.codingblocks.com/s/63809

1 Like
#11

can you post the link to the repo?

#12

@hardik.somani02 you can refer this.

#13

Node *buildtree()
{
queue<Node *>q;
int d;
cin>>d;
Node *root=new Node(d);

	q.push(root);
	int c1,c2;
	while(!q.empty())
	{
	cin>>c1>>c2;
	Node *f=q.front();
	q.pop();
	if(c1!=-1)
	{
	f->left=new Node(c1);
	q.push(f->left);
	}
	if(c2!=-1)
	{
		f->right=new Node(c2);
		q.push(f->right);
	}
	}
	return root;
}