# Number of different increasing binary trees

This is a homework question that I am unable to solve. Any help would be really appreciated.

Given $B$ an increasing binary tree with root $r$ and $n$ nodes labelled $1, 2, . . . , n$ such that on every path from root $r$ to a node, the labelling is increasing.

Prove that there are $n!$ different increasing binary trees.

Obviously, the root can only contain the smallest number $1$. Then $2$ can be placed in two positions, either as left or right child. Once this position is fixed, how many positions can $3$ go? Etcetera.