How to solve in o(n) time?

#1

I know that inorder traversal is sorted form of all numbers in a BST and we are already given a pre-order traversal so we can make the tree by combining them in o(n) time. But to find inorder traversal I will need to sort the preorder traversal which will itself take O(nlogn) time then how will I be able to solve the problem in O(n) time ?

#2

hi @alok.maurya

yes you can also solve this in 0(n)

hint :use the same apprach as you done while solving a problem
whether given tree is bst or not

The trick is to set a range {min … max} for every node. Initialize the range as {INT_MIN … INT_MAX}. The first node will definitely be in range, so create root node. To construct the left subtree, set the range as {INT_MIN …root->data}. If a values is in the range {INT_MIN … root->data}, the values is part part of left subtree. To construct the right subtree, set the range as {root->data…max … INT_MAX}.

#3

I understand the approach but need help with the code, please share the relevant code with me।

#4

@alok.maurya
first try at your own because this will be benificial for you
even if your are not able to implement this approach
i will help you through code as well

#5

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.