Labeled binary tree

Question

Number of labeled binary trees are there on vertices {1,2,3,4} that have only vertex 1 as leaf and every binary trees has 4 nodes are _______.

Comments

You may refer this diagram for better clarity.

---

It look like binary search tree, what are the case where we can make this diagram in binary tree.please clear this

Answer 1

We have $4$ nodes out of which $1$ is a leaf and there are no mode leaf nodes. So, we must have $4$ levels with one node in each. Each node in levels $2$, $3$ and $4$ have two choices- either to be left child or right child. So, totally $2 \times 2 \times 2 = 8$ ways. Now, $2,3,4$ can be permuted in any order in first $3$ levels and each permutation gives a different binary tree. So, total number of binary trees $= 8 \times 3! = 48$.

Answer 2

lets Vertex 1 is Leaf & it is fixed.
Exactly one leaf means at each level will be one & only one node..

Except root every node have 2 choices : 1. Left node 2. Right node
Total 4 nodes, so Number of possible combination for unlabeled tree are 2*2*2 = 8

We have to find Number of Labeled tree so multiply 8 by 3!
= 8*3! = 48

Comments

if 1 is not a fixed leaf then it is  2*2*2*2*4!   ??

---

yes..

---

@Arjun. We can choose leaf node in 4C1 ways ..is not it!!!