CODEWITHSUNDEEP
javabinary-search-treepreorderpostorder
Jeff_Storm
Jeff_Storm

Reputation: 1

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

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 :

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?

Upvotes: 0

Views: 543

Answers (1)

NoobEditor
NoobEditor

Reputation: 15911

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 :)

Upvotes: 0

Related Questions