# BST PreOrder to PostOrder

### BST PreOrder to PostOrder

##### 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`
• Create stack to hold smaller node
• Push `array `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
```
Author: