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.
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityhow 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.
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.