Preorder to Postorder Traversal

Problem Statement

Given an array that represents the preorder traversal of a binary search tree, write a program to find the postorder traversal of the BST.

Example

The preorder of a BST is given below: preorder[] = {10, 5, 8, 25, 47} The postorder for the example will be: postorder[] = {8, 5, 47, 25, 10}

Example Explanation

Input/Output

Input An array of size N represents the preorder traversal of a BST.

Output The postorder traversal of the given BST.

Constraints

$1 <= N <= 10^{3}$
$1 <= arr[i] <= 10^{4}$

Algorithm 1 - Simple Approach

• Step 1 - Construct a Binary Search Tree from the given preorder traversal using the function 'constructBST'.
• Step 2 - Perform postorder traversal on the constructed BST.

Code Implementation

C++

Java

Python

Output

Time Complexity

Time Complexity to construct BST is O($N^2$). Time complexity to find out the postorder traversal of the constructed BST is O(N) where N is no of the nodes in a binary tree. Thus, the overall time complexity of converting preorder to postorder traversal using this approach will be O($N^2$).

Space Complexity

The space complexity of this approach is O(N) where N is the extra space required for the set visited.

Algorithm 2 - Efficient Approach

In this approach of converting preorder to postorder traversal construction of a tree is avoided.

• The preorder array is traversed to maintain a range in which the current element should lie.
• In preorder traversal, the first element or root is stored as it lies in the initial range.
• Next, recursive calls are made for the left and right subtrees respectively. Then, the value of the root is printed.
  • For left subtree range is minval to root->data.
  • For right subtree range is root->data to maxval.
  • If the element considered lies outside the range specified, then it does not belong to a current subtree. Such recursive calls are returned until the correct position of that element is not found.

Code Implementation

C++

Java

Python

Output

Time Complexity

Since every node is traversed once, the time complexity for this approach is O(N), where N is the number of nodes.

Space Complexity

Due to the use of a call stack, the time complexity of this approach is O(N).

Algorithm 3 - Using Iteration and Recursion

The conversion of preorder to postorder traversal can also be done using iteration and recursion.

• Step 1 - Preorder can be represented as root -> left -> right and postOrder can be represented as left -> right -> root.
• Step 2 - A loop is used, and the last element of the left group is taken as the pivot element. The pivot is the point from which the array will be rotated. It is found by finding the index of the smallest element greater than the root.
• Step 3 - Consider the left section as elements from index 1 to index before pivot.
• Step 4 - Consider the right section as elements in between the last index and pivot.
• Step 5 - Repeat step 4 recursively till both the left and right sections have at most 1 element. Print the only element in the section.
• Step 6 - Finally, print the element at index 0.

Code Implementation

C++

Java

Python

Output

Time Complexity

For the execution of this approach, the array consisting of the preorder traversal elements is traversed to find the pivot in O(N). The rotation also takes O(N) time causing the overall time complexity for the Preorder function to be O(N). However, since the function is called recursively the overall time complexity will be O($N^2$).

Space Complexity

The Preorder function is called recursively which creates a new array every time it is called. Hence, the overall space complexity for this approach will be O($N^2$).