i need to make tree from level order? if yes then how can i do it?
I need to make tree?
Yes you need to do a level order traversal and display the first node at each level for left view
i think you have not read my question correctly, please check again my question then answer it
How is the input given?
If different levels are given in different lines then no need to make tree, you just need the first element of each line.
If all levels are given in the same line then break it level wise and do as for the previous.
If tree is given then you need the leftmost node at each level and for that you need to do level order traversal.
As here it is given level order in a single line, you need to break it into different levels based on the number of elements in each level. Store the elements in a 2-d matrix and then print out the first column.
1 2 3 4 5 -1 6 -1 -1 -1 -1 -1 -1
becomes
1
2 3
4 5 -1 6
-1 -1 -1-1-1-1
So left view is 1 2 4
this is not best solution, i want to know how can i make binary tree from given input, then i will apply logic on tree from root node.???
please read my question i asked how to make tree from given level order traversal , i think you have not read my question carefully. Please give me ans , i will not check dicussion forum in every five minutes. also m not getting any notification.
To make a tree from given level order traversal
- Note that the given level order traversal is for a complete binary tree where null nodes are represented by -1.
- We already know the number of nodes at each level (1 at level 1, 2 at level 2, 2^(i-1) at level i), hence we know from which element in the level order the next level starts.
- Now we just traverse the level order, knowing at what position the child nodes at level i+1 will be for a node at level i.
- Create tree by linking the nodes with their child nodes, replacing -1 with null nodes.
While creating the tree, you would also have to apply the check for whether the given node is a null node or not as null cannot have child
not able to understand how to build tree , i think it should be given in question , but not why?
Because a tree is not required to be built from the level order traversal to do this question.
I only described the tree because you insisted on that. The correct answer is the previous answer given by me to which you have said
okay, if root is given of binary tree, then you logic will not work ryt??
that’s why i am try built tree.
Either tree will be given or a traversal will be given
In either of the case you do not have to “build” the tree, just traverse what is given.
If tree is given, do a level order traversal of the tree, storing different levels in different queues, and then printing the first element of each queue.
In this question the level order traversal has already been done for you by the question.
there is any other solution ?? can i solve in constant space??in level order traversal , need n space for queue
No
Without storing the elements, how can you print them?
i think you don’t know recursive solution
Bhai to usme bhi to space use hi kar raha hai tu stack mei call karke
Plus it would be inefficent since between time and space, time has a higher priority
Thats why dynamic programming became a concept
ok , stack will be failed only for very large size of tree.
but it will be better for small size of tree as compared to iterative solution???
and time is O(n) in both cases either iterative or recursion
1 Like
if input is 1 2 3 -1 -1 5 6
then matrix is:
1
2 3
-1 -1 5 6
print only first column , then answer is 1,2??? please correct me if i am wrong?
No it will be 1,2,5 since both the children for 2 are null(-1) and so the first element viewable from the left would be the left child of 3 which is 5
but you said print the first column only , and you also store -1 in 2-d matrix.???
you can see your example
Store the elements in a 2-d matrix and then print out the first column.
1 2 3 4 5 -1 6 -1 -1 -1 -1 -1 -1
becomes
1
2 3
4 5 -1 6
-1 -1 -1-1-1-1