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