Structual induction on mirror(mirror t) = t

Question

I have to prove that for all binary trees $t$ the following property holds: $$mirror(mirror(t))=t$$ $mirror(t)$ is defined as:

$$mirror(t) =\begin{cases} Empty, & \text{if $t$ is Empty} \\ Node(mirror(r),v,mirror(l)) & \text{if $t$ is a Node(l,v,r)} \end{cases}$$

Base Case: $t=Empty$

$$(mirror(mirror(Empty))=mirror(Empty)=Empty=Empty$$

Step Case:$t=Node(l,v,r)$

$$mirror(mirror(Node(l,v,r))=Node(l,v,r)$$

Now i am a little bit confused, how i am able to use the induction hypothesis in my prove. The next steps are to use the definition of $mirror():$

$$mirror(mirror(Node(l,v,r))=Node(l,v,r)$$ $$mirror(mirror(Node(l,v,r))=mirror(Node(mirror(r),v,mirror(l)))= Node(mirror(mirror(l)),v,mirror(mirror(r)))$$

Now i am stuck. How can I use the IH in my Prove?

Thank you

Answer 1

The induction hypothesis in this case is that $mirror(mirror(t))$ holds for the subtrees $l$ and $r$. Hence, we get $$mirror(mirror(Node(l,v,r))) = Node(mirror(mirror(l)),v,mirror(mirror(r))) = Node(l,v,r),$$ which is what we wanted to prove.