Complete Binary Tree A
balanced
binary
tree
is
a
full
binary
tree
in
which
every
leaf
is
either
at
level
l
or
l-­1
for
some
positive
integer
l.
The
set
of
balanced
binary
trees
is
defined
recursively
by:
Basis
step:
A
single
vertex
is
a
balanced
binary
tree.
The
tree
with
two
vertices,
namely
a
root
and
a
left
child
(a
leaf)
is
a
balanced
binary
tree.
The
tree
with
two
vertices,
namely
a
root
and
a
right
child
(a
leaf)
is
a
balanced
binary
tree.
Recursive
step:
A
balanced
binary
tree
T=
T1

T2
consists
of
a
new
root
r
together
with
edges
connecting
the
r
to
each
of
the
roots,
r1
and
r2,
of
two
balanced
binary
trees,
T1
(the
left
subtree)
and
T2
(the
right
subtree),
respectively,
where
the
leaves
of
T1
and
T2
are
at
either
level
l
or
l‐1
for
some
positive
integer
l.
Draw
the
balanced
binary
trees
formed
by
0,
1
and
2
applications
of
the
recursive
step
of
the
recursive
definition
above.
 A: Let $S,L,R$ be the BBTs with a single vertex, a root and a left child, and a root and a right child. These are the trees formed by zero applications of the recursive step. For trees formed by one application of the recursive step, we have a-priori nine possibilities: $$S\square S,S\square L,S\square R,L\square S,L\square L,L\square R,R\square S,R\square L,R\square R.$$
However, we need to check that the condition that all leaves be on two adjacent levels holds. Since the leaves of $S,L,R$ are all on levels $0,1$, this condition always holds. When considering trees formed by two applications, there will be cases in which the condition doesn't hold, for example $S\square(S \square L)$, in which leaves are at levels $1,2,3$.
The most difficult case, of two applications, I leave to you. There are two (symmetric) possibilities two consider: $\alpha\square(\beta\square\gamma)$ and $(\alpha\square\beta)\square\gamma$, where $\alpha,\beta,\gamma \in \{S,L,R\}$. Hence a-priori there are 54 possibilities, but as mentioned above, some of them will be ruled out.
