Output Post-Order Binary Search Tree from Given Pre-Order input without constructing tree or using recursions

0
votes

Problem Description: (language is java)

Given an input array representing a preorder traversal of a binary search tree, output a postorder traversal of the BST.

Catch :

  • No construction of BST nodes.
  • No recursions.
  • O(n) running time.

I have tried figuring it out for hours, but still have no clues.
The hardest part is without using the tree node struct.
Anyone have ideas?

1
javabinary-search-treepreorderpostorder

1 Answers

0
votes

here is a hint :

In preorder traversal, the first element of the array is always going to be the root of the tree,
so if, NodeElemnts[] is given array, then NodeElemnts[0] will be the root of the trees

then, left node is located at 2n+1 and right node is located at 2n+2, n being the index of current array.

for Pre to Post :

[root][leftChild][rightChild] (pre) -> [leftChild][rightChild][root] (post) .....think BFS :)