We can define a complete binary tree to be one that has all leaf nodes at the same depth ~d~. The figure below depicts a complete binary tree with depth ~3~.

We can likewise define a partially complete binary tree to be one in which all leaf nodes are at depth ~d~ or depth ~d-1~, and where all leaf nodes at depth ~d~ form a contiguous block at the leftmost end of the tree. One such example is shown below with depth ~4~. Note that all complete binary trees are also considered to be partially complete.

This task asks for the smallest number of operations required to transform a given binary tree into a partially complete binary tree. The only operation available is to swap the left and right children of a node. To solve this task, we define the following recursive functions:

• ~h(t)~, which returns the height of a subtree, ~t~.
• ~c(t)~, which returns the fewest number of swaps required to make the subtree ~t~ complete. This will be ~0~ if the given subtree is already complete, or ~\infty~ otherwise (since if a tree is not already complete, it can never be made complete). To calculate this, we simply check whether the subtree's two immediate children are complete subtrees and whether they have the same height.
• ~p(t)~, which returns the fewest number of swaps required to make the given subtree partially complete, or ~\infty~ if this is not possible. Let ~l~ and ~r~ denote the left and right subtrees of ~t~. We calculate ~p(t)~ by taking the minimum of the following:
  • The result of ~c(t)~;
  • If ~h(l) = h(r)+1~, then consider ~p(l)+c(r)~;
  • If ~h(l) = h(r)-1~, then consider ~c(l)+p(r)+1~;
  • If ~h(l) = h(r)~, then consider both ~c(l)+p(r)~ and ~p(l)+c(r)+1~.

Each of these functions is calculated recursively for each subtree, working upwards from the leaves to the root of the tree. The final solution has a running time of ~\mathcal O(n)~, where ~n~ is the number of nodes in the tree.