I am studying tree traversals and I've got to know that we can uniquely determine the binary tree if their:

Case 1. Preorder & inorder traversals are given or

Case 2. postorder & inorder traversals are given

We can not determine the tree if only one of the traversals are given because there will be finitely many trees possible.

My question is that, is there a way to calculate the number of trees possible?


Your question probably assumes that the nodes of the tree all contain different values. If we have a tree with $n$ nodes all of whose have the same label $x$, then we can't tell what tree we're looking at by observing the traversals, as we always get just a series of $x$'s, independent of what the tree shape is or what traversal we use. So I assume the labels are all different.

Use the traversal to generate a list of all the elements of the tree $[x_1, \ldots, x_n]$. Now, which trees are possible with this particular traversal? Pick any tree with $n$ elements and place the labels $x_i$ into the nodes so that for that tree you'll get them back in the order $[x_1, \ldots, x_n]$. This shows that, if we only have one of the traversals available, any tree shape is possible, as long as it has the correct number of nodes $n$. So the answer is that there are $C_n$ such trees, where $$C_n = \frac{1}{n+ 1}{2 n \choose n}$$ is the $n$-th Catalan number.


Total number of possible Binary Search Trees with n different keys = Catalan number Cn = (2n)!/(n+1)!*n!

For n = 0, 1, 2, 3, … values of Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …. So are numbers of Binary Search Trees.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.