Question

Which of the following statement is not correct.
I. Number of unlabeled binary trees are same as number of binary search trees for any number of vertices.
II. Postorder traversal takes O(V) time for V vertices in a binary tree.
III. Preorder and postorder Traversal combination can always uniquely construct a binary tree.
IV. In a binary search tree, the smallest vertex always lies is one of leaf nodes.

Answer 1

I. Since in the unlabeled binary tree, total no. of possible trees are $={}^{2n}{C}_n/n+1$, which is some as B.S.T. Since there is only one way to fill a B.S.T. when we have a specific structure, But it changes in the case of binary tree as the number of possible trees will become =(${}^{2n}{C}_n/n+1\ast n!$), so the statement is true.
II. Post order, Inorder & preorder traversal takes O(V) time
III. Preorder and postorder traversal combination can not construct a binary tree uniquely.
IV. Smallest node is the root node