### BST PreOrder to PostOrder

##### Given an array representing preOrder traversal of BST, print its postOrder traversal.

##### Solution:

- First create BST from give preOrder array
- Second traverse the traverse create BST in post order
- The main of this problem is creation of BST from preorder array
- That we can do by recursive and non recursive ways

##### Recursive Algorithm:

- Recursive function with argument – array, start index and end index
- if start > end then return null
- Set root = Root(array[start])
- Find position i in array from start to end index such that array[i] > array[start]
- Set leftChild = Recursive Call (array, start + 1, i-1)
- Set rightChild = Recursive Call (array, i, end)
- Update root left and right children
- Return root

##### Non-Recursive Algorithm:

- Create
`root_node with array[0]`

- Create stack to hold smaller node
- Push
`array[0]`

in stack - Iterate array from index 1 to N
- Create tree_node with array [i]
- Set
`temp = null`

`If stack.top < array[i] and stack is not empty`

then.`temp = stack.pop`

- If
`temp == null`

then,`temp = stack.top`

`temp.left = tree_node`

`temp = temp.left`

- else
`temp.right = tree_node`

`temp = temp.right`

`stack.push(temp)`

`return root_node`

Latest Source Code:

Github: BSTPreOrderToPostOrder.java

**Output:**

35 30 100 80 40 35 30 100 80 40 4 9 8 11 15 10 4 9 8 11 15 10 35 32 30 120 100 90 80 40 35 32 30 120 100 90 80 40