Substituting value $n=2$ in Construction theorem of Type II Optimal normal basis
For $n=2$, ONB of Type II exist for $\mathbb{F}_{2^n}$ over $\mathbb{F}_2$. because, 2 is primitive $\mathbb{Z}_5$. By theorem, we have to find primitive 5th root of unity in $\mathbb{F}_{2^4}$.i.e., $$\gamma=t^3, t^3+t^2, t^3+t, t^3+t^2+t+1$$ and $$\gamma^{-1}=t^3+t^2+t+1, t^3+t, t^3+t^2, t^3$$
where $t$ is root of defining polynomial $x^4+x+1$.
Hence, $$\alpha=\gamma+\gamma^{-1}=t^2+t+1 \textit{ or } t^2+t$$ even if we reducing both polynomials over defining polynomial $(x^2+x+1)$, we get $0$ or $1$ respectively.
But, these are not generator of Type II optimal normal basis of $\mathbb{F}_{2^2}$ over $\mathbb{F}_2$.
My doubt is that am I wrong somewhere. For $n=3$ also, I was getting $\alpha=t^5 + t + 1$, which is not even an element of $GF(2^3)$. Upon reduction over defining polynomial $x^3+x+1$, I am getting $1$.
Your confusion seems to arise from having a wrong idea about the relation of the elements of the fields $\Bbb{F}_{16}=GF(16)$ and its subfield $\Bbb{F}_4=GF(4)$. It is correct to construct these two fields as quotient fields of the polynomial ring by moding out the ideal generated by the defining polynomial: $$ \Bbb{F}_{16}=\Bbb{F}_2[x]/\langle x^4+x+1\rangle $$ and $$ \Bbb{F}_4=\Bbb{F}_2[x]/\langle x^2+x+1\rangle. $$ But you have to realize that this is insufficient for the purposes of identifying $\Bbb{F}_4$ as a subfield (= a special kind of a subset) of $\Bbb{F}_{16}$, which is what the task at hand requires. In other words, the $x$, or more accurately the coset $x+\langle x^4+x+1\rangle$, an element of $\Bbb{F}_{16}$ that you denoted by $t$, has nothing whatsoever to do with the $x$, more accurately the coset $x+\langle x^2+x+1\rangle\in\Bbb{F}_4$. Yet in other words, your $t$ is a quantity that satisfies the relation $t^4+t+1=0$, and this is unrelated to the equation $x^2+x+1=0$.
To make progress, let's denote the coset $x+\langle x^2+x+1\rangle\in \Bbb{F}_4$ by $s$, so $s^2+s+1=0$.
Your calculation started out fine. You correctly identified $\gamma=t^3$ as well as its non-trivial powers as the fifth roots of unity in $\Bbb{F}_4$. You correctly calculated $\alpha=\gamma+\gamma^{-1}$ to be either $t^2+t+1$ or $t^2+t$. The problems started, when you tried to think of $\alpha$ as an element of $\Bbb{F}_4$. I don't know how much your source discusses this step, but next you need to figure out what $s$ is inside $\Bbb{F}_{16}$? This is not difficult, but it is not entirely trivial in the general case. Here we can manage easily, because the fields are very small. The multiplicative group of $\Bbb{F}_4$ is cyclic of order $4-1=3$, so the non-trivial elements (excluding $0$ and $1$ here) of $\Bbb{F}_4$ have order $3$. We used a primitive polynomial in constructing $\Bbb{F}_{16}$, so we know (and can easily verify, your $t$ is what I denoted $\gamma$) that $t$ has order $15$. This implies that $t^5$ and $t^{10}$ are non-trivial roots of unity of order three. We easily calculate (use the relation $t^4+t+1=0$, or take a peek at my old answer again) that $$ t^5=t\cdot t^4=t(t+1)=t^2+t $$ and $$ t^{10}=(t^5)^2=(t^2+t)^2=t^4+t^2=t^2+t+1. $$ So we have $$ \Bbb{F}_4=\{0,1,t^2+t,t^2+t+1\}\subset \Bbb{F}_{16}. $$ But we need to find $s$ in there!? The only thing we can use is the given fact that $s$ satisfies the equation $s^2+s+1=0$. At this point I invite you to check yourself (again using $t^4+t+1=0$) that both $t^2+t$ and $t^2+t+1$ are solutions of the equation $x^2+x+1=0$. Which one is $s$? We cannot tell!!! Galois theory (you may not have heard of that piece of algebra) says, loosely, that we cannot distinguish between the zeros of an irreducible polynomial by algebraic means, so you can use either $s=t^2+t$ or $s=t^2+t+1$. Observe that it does not matter in the end, because we end up with the optimal normal basis $\{s,s^2=s+1\}$ in either case. In the old answer I wrote $\beta$ instead of $s$.
It's less clear what went wrong in your calculation with $\Bbb{F}_8$. We can construct it as $\Bbb{F}_8=\Bbb{F}_2(r)$, where $r$ is a root of $x^3+x+1$, so we have $r^3+r+1=0$. It is easy to verify that $r$ is also a root of unity of order seven. Take a peek at that old answer of mine again. I denoted $r$ by $\alpha$ back in the day.
Consequently $1=r^3+r=r(r^2+1)$, and we can solve $r^{-1}=r^2+1$. It follows that $$ r+r^{-1}=r^2+r+1, $$ and consulting the table in my old answer we can also write it as $r^2+r+1=r^5$ should that be more convenient for some calculation. Anyway, it follows that $\{r^5,r^{10}=r^3,r^6\}$ is an optimal normal basis of $\Bbb{F}_8$ over $\Bbb{F}_2$. It is actually the only normal basis of this extension, so you have to use it (assuming you want a normal basis for some implementation) irrespective of whether it's optimal or not.