algorithm mirror

Algorithm

Mirror-Binary-Tree(T)
1 if T =/= nil then
2 T.Left = Mirror-Binary-Tree(T.Right)
3 T.Right= Mirror-Binary-Tree(T.Left)
4 return T


It take constant time C to process a node with no child.
T(1) = C.

For all other nodes, we have
T(n) = T(a) + T(n-1-a) + D, for all possible split of the tree, with a nodes on the left and n - 1 - a nodes on the right.

Let S(n) be the statement T(n) = O(n).
S(1) is true because T(1) = C = O(1).

Assume S(n) to be true for all n <= k.
For n = k+1, we have
T(n) = T(a) + T(n - 1 - a) + D = O(a) + O(n - 1 - a) + O(1) = O(n).

Therefore, by the principle of (strong) Mathematical Induction, the statement S(n) is true for all positive integer n.

Notice this running time is also the lower bound for this problem because you will need to produce the output (which has size n) anyway. Producing the output takes time proportional to the size of the tree = O(n).