how many BST exist with same postorder and inorder traversal?
I know that in binary tree (Not BST), it is one.
but i have a book from that said for BST it is CATALAN number. i become confused.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Your confusion might stem from this: The number of binary trees on $n$ vertices is $C_n$, the $n$-th Catalan number. Since in a BST, the left-right order of vertices is fixed, the number of BSTs with a given inorder traversal is also $C_n$. However, with the added restriction that the postorder traversal must be the same as the inorder traversal, the BST can only have left branches.
In more detail, recall that inorder = left-visit-right and postorder = left-right-visit.
If both traversals must be the same (visit is at the root) there can be no right subtree, and this is then the same at the left child, and so on. This leaves only one form: a tree with only children to the left.
What is your book stating, more precisely? Perhaps we can find the reason for the confusion.
answered Mar 3, 2015 at 14:33
-
$\begingroup$ my book said: we can make a tree with given Postorder and then assign nodes's label with inorder traversal. and it said so we can make any BST and the answer is all trees. $\endgroup$– mbagherMar 4, 2015 at 7:00