1 2 3 4 5 -1 6 -1 -1 -1 -1 -1 , what does these -1 ones in the iput mean and what approach should be followed to make a tree out of the given input
Tree left view problem
@AbhishekAhlawat1102
the input is given in level order format
1 -1 level
2 3-second level
…
you can construct the tree with the help of queue in the same way as you apply bfs using queue
then the problem can also be solved using simple recursive traversal. We can keep track of level of a node by passing a parameter to all recursive calls. The idea is to keep track of maximum level also. Whenever we see a node whose level is more than maximum level so far, we print the node because this is the first node in its level (Note that we traverse the left subtree before right subtree).
i know what approch to take but i donot know how to take input how i m supposed to take input with these -1 ones’s and what does the mean?
@AbhishekAhlawat1102
-1 represent null child
I will process the sample tree for you
input ;
1 2 3 4 5 -1 6 -1 -1 -1 -1 -1 -1
let queue be qt
qt:1
we take the first element of queue
and then take next two element from input and set left and right and add them to queue as well.
so our tree will be like
1
/ \
2 3
qt:2,3
again we extract first element of the queue which is 2
take next two element from input which are 4,5
set left and right child of node 2
so tree our will be like
. 1
. / \
. 2 3
. / \
4 . 5
and add 4,5 to the queue
qt:3,4,5
now we take first element of queue again and the next two input which -1 and 6
since we got -1 we will make the left child of 3 as null and right child of 3 as 6
and add only 6 to the queue
so finally our tree will be like
. 1
. / . \
. 2 . . 3
. / \ . . \
4 . 5 … 6
and element in queue will be
qt: 4,5,6
now we extract 4 and take next two element from the input which are -1, -1;
we set both left and right as null.
so our tree remain same
. 1
. / . \
. 2 . . 3
. / \ . . \
4 . 5 … 6
qt:5,6
we take 5 and the next 2 element from the input which are again -1, -1
set both left child and right child of 5 as null
so tree remains same again
. 1
. / . \
. 2 . . 3
. / \ . . \
4 . 5 … 6
finally our queue will be
qt:6
we extract 6 and the next two elements from input which are again -1,-1
our final tree will be same
. 1
. / . \
. 2 . . 3
. / \ . . \
4 . 5 … 6
and our queue becomes empty and we stop there.
I HOPE THIS WILL HELP YOU UNDERSTAND HOW TO CONSTRUCT A TREE 
