2,365 views

3 Answers

Best answer
6 votes
6 votes

Whenever you see some question like this, just imagine the worst tree which you can form. For this lets take skew tree. If preorder and inorder of skew tree is given then it will take $O(n^2)$ time to create Binary tree.

This is an example of skew tree.

selected by
0 votes
0 votes
INORDER AND PREORDER ARE GIVEN.

SO FOR THE PURPOSE OF  FINDING THE ROOT NODE THAT CAN BE DONE IN O(1) TIME(COZ PREORDER GIVEN).

NOW OUR TASK IS FINDING THE LEFT SUBTREE AND RIGHT SUBTREEE...SO FOR THAT PURPOSE THE ELEMENT WHICH WE TAKEN AS ROOT...WE HAVE TO SEARCH THAT ELEMENT IN THE GIVEN INODER OF TREE..AND THIS LINEAR SEARCH TAKES O(N) TIME FOR ONE ELEMENT

REPEAT THIS PROCEDURE FOR ALL ELEMENTS...MEANS N times linear search is requird...so time complexity will be O(N^2)

Related questions

0 votes
0 votes
2 answers
3
0 votes
0 votes
6 answers
4
Umang Raman asked Sep 25, 2015
5,547 views
The in-order traversal of a tree resulted in FBGADCE. Then pre-order traversal would result in.a)FGBDECAb)ABFGCDEC)BFGCDEAd)AFGBDEC