CODEWITHSUNDEEP
algorithmdata-structuresbinary-search-treetree-traversal
SajjadSM
SajjadSM

Reputation: 73

How to recognize some binary search tree traversal belongs to post-order or in-order?

If the pre-order of a binary search tree is [P, A, R, S], How to recognize [R, S, A, P] belongs to in-order or post-order? If is post-order how to find out is (Left, Right, Root) or (Right, Left, Root)?

Upvotes: 4

Views: 113

Answers (2)

Jim Mischel
Jim Mischel

Reputation: 134125

If the pre-order traversal is [P, A, R, S], then P must be the root. And since it's a binary search tree, then A must be the left child and R and S must be in the right subtree. That gives you two possible trees:

      P                 P
    A   R            A     S
          S              R

A reverse post-order traversal of the second tree will provide the sequence [R, S, A, P].

Upvotes: 2

learner
learner

Reputation: 1982

In order of a binary search tree will always be in sorted order. As [R, S, A, P] is not in sorted order, it should be post order.

Upvotes: 2

Related Questions