Hi, I came across this problem that is giving me some trouble:

Given an array P that contains the pre-order traversal of a binary search tree of n nodes with distinct integer values, design an algorithm that runs in O(n) time and computes the post-order traversal of the tree.

I did write this algorithm :

1. If the preorder array has a length of zero or one, return it as the postorder array.

2. Store the first element of the preorder array, P[1], as the root.

3. Split the rest of the array (P[2] to P[n]) into the left and right subtrees. We can locate the pivot point, where the split occurs, using a modified binary search algorithm. In this version of the algorithm, we look for the first instance where the element in P is larger than the root. We save this index as the pivot.

4. Now that we know where the pivot is, we can split the array into the left and right subtrees, left = P[2] to P[pivot - 1] and right = P[pivot] to P[n].

5. Recursively apply the algorithm on the left and right subtrees. Take the return from the left and right subtrees, and combine them with the root, output(left) + output(right) + root. On each subtree, the roots are moved to the end of the array.

but I think mine runs in O(n*log(n)) instead of O(n). How would I accomplish this? Thank you for your time!