I ran into an interesting programming problem here

It basically boils down to the following: Given a postorder traversal (left, right, father) of a BST, give a reversed postorder traversal (right, left, father).

Some preliminary thoughts:

- A postorder traversal does not uniquely define a BST. Therefore, it's possible to somehow "tailor" a BST to fit some postorder

- If I take a BST, and switch all right links in it with left links and vice versa, and then traverse it in postorder, I'll get the reversed postorder of the original tree. This can somehow help with the solution, maybe.


Comments

comments powered by Disqus