CODEWITHSUNDEEP
data-structuresbinary-tree
shridatt
shridatt

Reputation: 926

Deriving Binary tree from postorder or preorder listing

I have a question regarding binary trees. so i know about preorder postorder and inorder that is used to construct the binary tree. Now how do i derive the inorder listing of a tree from a postorder listing of a tree or preorder listing of a tree.

Upvotes: 1

Views: 1047

Answers (1)

Antti Huima
Antti Huima

Reputation: 25522

You can't derive an inorder listing from a postorder listing because postorder listing does not provide enough information about the shape of the tree. You need two listings (e.g. postorder and preorder) in order to uniquely reconstruct the tree.

A simple counterexample:

postorder listing : A B C

This can be one of two trees

    C
    |      C
    B     / \
    |    A   B
    A

but the inorder listings for these two trees are A B C and A C B.

Upvotes: 2

Related Questions