Reputation: 73
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
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
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