Recall from Assignment $3$ the definition of a binary tree data structure: either an empty tree, or a node with two children that are trees.

Let T$($n$)$ denote the number of binary trees with n nodes. For example T$(3)=5$ because there are five binary trees with three nodes:

Background image

$-------------$

A full binary tree is a non$-$empty binary tree where every node has either two non$-$empty children $($i$.$e$.$ is a fully$-$internal node$)$ or two empty children $($i$.$e$.$ is a leaf$).$

$-------------$

A well$-$formed formula is in Negated normal form if it consists of just $,,$ and literals $($i$.$e$.$ propositional variables or negations of propositional variables$).$ For example, $($ p $($ q $$ r $))$ is in negated normal form; but $($ p $($ q $$ r $))$ is not.