Minimal, "natural" set of operations to manipulate a binary tree
It looks like the following set of four operations is sufficient.  They are also minimal / necessary in the sense that no single operation can be removed from the set.


right rotation at the root:

    .            .
   / \          / \
  .  z    =&gt;   x   .
 / \              / \
x   y            y   z

duplicating the tree
deleting the left branch
flipping the right grandchildren


By way of illustration (and a form of proof outline), I've written up a Haskell implementation.  Given a definition of a Tree structure and a TreeOp tree operation type:

data Tree a = Node (Tree a) (Tree a) | Leaf a
type TreeOp a = Tree a -&gt; Maybe (Tree a)


the primitive operations would be defined as:

rotateR, dup, deleteL, flipR :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing


We can define derived operations to flip the root's children (duplicate the tree, flip the right grandchildren, and delete the left branch):

flipC :: TreeOp a
flipC = dup &gt;=&gt; flipR &gt;=&gt; deleteL


Similarly, we can define an operation to duplicate the right branch:

dupR :: TreeOp a
dupR = dup &gt;=&gt; rotateR &gt;=&gt; flipR &gt;=&gt; deleteL &gt;=&gt; rotateR


as well as the symmetric variants of all the above operations:

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC &gt;=&gt; flipR &gt;=&gt; flipC
deleteR = flipC &gt;=&gt; deleteL
dupL = flipC &gt;=&gt; dupR &gt;=&gt; flipC
rotateL = flipR &gt;=&gt; flipC &gt;=&gt; rotateR &gt;=&gt; flipR &gt;=&gt; flipC


Finally, it will be helpful to have an operation for "interleaving" the grandchildren like so:

        ..           ..
       /  \         /  \
      .    .       .    .
     / \  / \     / \  / \
     w x  y z     w y  x z


The best implementation I could come up with was:

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  &gt;=&gt; rotateR &gt;=&gt; flipL &gt;=&gt; rotateR &gt;=&gt; deleteL &gt;=&gt; rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  &gt;=&gt; flipL &gt;=&gt; rotateR &gt;=&gt; flipL &gt;=&gt; rotateR &gt;=&gt; deleteL &gt;=&gt; rotateL &gt;=&gt; flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  &gt;=&gt; rotateL &gt;=&gt; flipR &gt;=&gt; rotateL &gt;=&gt; deleteR &gt;=&gt; rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  &gt;=&gt; flipR &gt;=&gt; rotateL &gt;=&gt; flipR &gt;=&gt; rotateL &gt;=&gt; deleteR &gt;=&gt; rotateR &gt;=&gt; flipR


With interleave, it's easy to define operations to rotate the left and right subtrees of the root independently:

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR &gt;=&gt; flipL &gt;=&gt; interleave &gt;=&gt; rotateL &gt;=&gt; flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL &gt;=&gt; rotateR &gt;=&gt; interleave &gt;=&gt; flipL &gt;=&gt; rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC &gt;=&gt; rotateLR &gt;=&gt; flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC &gt;=&gt; rotateLL &gt;=&gt; flipC


Using a helper to apply an operation repeatedly until it no longer works:

untilDone :: (a -&gt; Maybe a) -&gt; a -&gt; a
untilDone op t = maybe t (untilDone op) (op t)


we can turn any tree into an in-order traversal "cons-list-like" normal form:

toList :: Tree a -&gt; Tree a
toList 
  = untilDone rotateR 
    &gt;&gt;&gt; untilDone (untilDone rotateRL &gt;&gt;&gt; rotateL)
    &gt;&gt;&gt; untilDone rotateR


meaning that, for any tree t whose in-order traversal of leaves is, say, [1,2,3,4,5], the result of toList t will be:

Node (Leaf 1) (Node (Leaf 2) (Node (Leaf 3) (Node (Leaf 4) (Leaf 5))))


Now, this normal form is just a zipper under the rotateL and rotateR operations -- we can rotateR it to any point in the list, with the "rest" of the list elements on the right branch in normal form, and the preceding elements on the left branch in an "inverted" normal form (with leaves on the right branches instead of the left).

Applying interleave to such a zipper will swap adjacent elements at the zipper's cursor in the general case, though the following function also handles the corner cases where interleave fails because the left or right branch is just a leaf:

swapLeaves :: TreeOp a
swapLeaves = interleave 
  `orTry` (rotateR &gt;=&gt; flipR &gt;=&gt; rotateL)
  `orTry` (rotateL &gt;=&gt; flipL &gt;=&gt; rotateR)


Here, orTry isn't a separate operation -- it's just a conditional control structure that handles the case where a generalized operation fails because, say, the left branch is only a leaf instead of a larger inverted cons list:

orTry :: TreeOp a -&gt; TreeOp a -&gt; TreeOp a
orTry op1 op2 t = op1 t &lt;|&gt; op2 t
infixl 1 `orTry`


We can also duplicate the element to the left of the cursor with:

dupLeaf :: TreeOp a
dupLeaf = (flipL &gt;=&gt; rotateR &gt;=&gt; dupL &gt;=&gt; rotateL &gt;=&gt; flipL &gt;=&gt; rotateLR) 
  `orTry` dupL


This doesn't handle two corner cases: we can duplicate the rightmost element (i.e., duplicate an element to the right of the cursor) with a swapLeaves &gt;=&gt; dupLeaf =&gt; swapLeaves =&gt; rotateR =&gt; swapLeaves combination, and if the tree is a lone leaf, we can just duplicate it with dup.

We can delete the element to the left of the cursor with:

deleteLeaf :: TreeOp a
deleteLeaf = (flipL &gt;=&gt; rotateR &gt;=&gt; deleteL) `orTry` deleteL


and the last element with a swapLeaves &gt;=&gt; deleteLeaf combination`.

I think it's clear that with there operations to swap, duplicate, and delete leaves together with rotations through the zipper, we can turn any in-order cons list into any other in-order cons list constructed from a subset of its elements.

And, since toList uses only reversible operations, it follows that we can reconstruct the final tree from its in-order cons list, so I think that probably completes the proof that these operations are sufficient.

To establish that they're "minimal" / necessary, we need to show that dropping any one of the primitive operations would make it impossible to handle some case.  It's easy to see that dup and deleteL are necessary, as they're the only operations that can add or remove leaves, respectively.  With the exception of rotateL, all the other operations preserve the binary tree property of "perfection" or "perfect balance" (i.e., the property of having all leaves at the same level), so rotateR is necessary to create an unbalanced tree from a perfectly balanced one.  And finally, flipR is necessary as no remaining operations can change the in-order traversal of a tree's leaves (oops -- actually, this isn't convincing, since dup and deleteL can do this; I'll need to think about this one).

Anyway, here's the full code to play with:

{-# OPTIONS_GHC -Wall #-}
import Data.Maybe (fromJust)
import Control.Monad
import Control.Applicative
import Control.Arrow ((&gt;&gt;&gt;))
data Tree a = Node (Tree a) (Tree a) | Leaf a
data Side = L | R
type TreeOp a = Tree a -&gt; Maybe (Tree a)

rotateR, dup, deleteL, flipR, interleave :: TreeOp a

rotateR (Node (Node x y) z) = Just $ Node x (Node y z)
rotateR _ = Nothing

dup t = Just $ Node t t

deleteL (Node _ x) = Just x
deleteL _ = Nothing

flipR (Node x (Node y z)) = Just $ Node x (Node z y)
flipR _ = Nothing

flipC :: TreeOp a
flipC = dup &gt;=&gt; flipR &gt;=&gt; deleteL

dupR :: TreeOp a
dupR = dup &gt;=&gt; rotateR &gt;=&gt; flipR &gt;=&gt; deleteL &gt;=&gt; rotateR

flipL, deleteR, dupL, rotateL :: TreeOp a
flipL = flipC &gt;=&gt; flipR &gt;=&gt; flipC
deleteR = flipC &gt;=&gt; deleteL
dupL = flipC &gt;=&gt; dupR &gt;=&gt; flipC
rotateL = flipR &gt;=&gt; flipC &gt;=&gt; rotateR &gt;=&gt; flipR &gt;=&gt; flipC

interleave =
  -- duplicate the whole tree [[A B] [C D]] [[A B] [C D]]
  dup
  -- select first grandchild:  [[A] [C D]] [[A B] [C D]]
  &gt;=&gt; rotateR &gt;=&gt; flipL &gt;=&gt; rotateR &gt;=&gt; deleteL &gt;=&gt; rotateL
  -- select second grandchild: [[A] [C]] [[A B] [C D]]
  &gt;=&gt; flipL &gt;=&gt; rotateR &gt;=&gt; flipL &gt;=&gt; rotateR &gt;=&gt; deleteL &gt;=&gt; rotateL &gt;=&gt; flipL
  -- select fourth grandchild: [[A] [C]] [[A B] [D]]
  &gt;=&gt; rotateL &gt;=&gt; flipR &gt;=&gt; rotateL &gt;=&gt; deleteR &gt;=&gt; rotateR
  -- select third grandchild:  [[A] [C]] [[B] [D]]
  &gt;=&gt; flipR &gt;=&gt; rotateL &gt;=&gt; flipR &gt;=&gt; rotateL &gt;=&gt; deleteR &gt;=&gt; rotateR &gt;=&gt; flipR

rotateLR, rotateLL, rotateRL, rotateRR :: TreeOp a
-- rotate left subtree right (i.e., apply `rotateR` to left child)
rotateLR = rotateR &gt;=&gt; flipL &gt;=&gt; interleave &gt;=&gt; rotateL &gt;=&gt; flipL
-- rotate left subtree left (i.e., apply 'rotateL' to left child)
rotateLL = flipL &gt;=&gt; rotateR &gt;=&gt; interleave &gt;=&gt; flipL &gt;=&gt; rotateL
-- rotate right subtree right (i.e., apply `rotateR` to right child)
rotateRR = flipC &gt;=&gt; rotateLR &gt;=&gt; flipC
-- rotate right subtree left (i.e., apply `rotateL` to right child)
rotateRL = flipC &gt;=&gt; rotateLL &gt;=&gt; flipC

untilDone :: (a -&gt; Maybe a) -&gt; a -&gt; a
untilDone op t = maybe t (untilDone op) (op t)

toList :: Tree a -&gt; Tree a
toList
  = untilDone rotateR
    &gt;&gt;&gt; untilDone (untilDone rotateRR &gt;&gt;&gt; rotateL)
    &gt;&gt;&gt; untilDone rotateR

swapLeaves :: TreeOp a
swapLeaves = interleave
  `orTry` (rotateR &gt;=&gt; flipR &gt;=&gt; rotateL)
  `orTry` (rotateL &gt;=&gt; flipL &gt;=&gt; rotateR)

orTry :: TreeOp a -&gt; TreeOp a -&gt; TreeOp a
orTry op1 op2 t = op1 t &lt;|&gt; op2 t
infixl 1 `orTry`

dupLeaf :: TreeOp a
dupLeaf = (flipL &gt;=&gt; rotateR &gt;=&gt; dupL &gt;=&gt; rotateL &gt;=&gt; flipL &gt;=&gt; rotateLL)
  `orTry` dupL `orTry` dup

deleteLeaf :: TreeOp a
deleteLeaf = (flipL &gt;=&gt; rotateR &gt;=&gt; deleteL) `orTry` deleteL

pprint :: (Show a) =&gt; Tree a -&gt; IO ()
pprint = putStrLn . unlines . pshow
pshow :: (Show a) =&gt; Tree a -&gt; [String]
pshow t = case t of
  Leaf x -&gt; [center 5 $ show x]
  Node x y -&gt; bar ++ xy'
    where x' = pshow x
          y' = pshow y
          xy' = hjoin x' y'
          lft = width x' `div` 2
          rgt = width y' `div` 2
          rest = width xy' - lft - rgt
          bar = [ justify lft rgt $  '.' : replicate (rest - 2) '-' ++ "."
                , justify lft rgt $  '|' : spaces (rest - 2) ++ "|" ]
  where
    spaces = (`replicate` ' ')
    justify l r str = spaces l ++ str ++ spaces r
    width = length . head
    center n str = justify l (l+u) str
      where (l, u) = (n - length str) `divMod` 2
    hjoin x y = go x y
      where wx = width x
            wy = width y
            go (l:ls) (r:rs) = (l ++ r) : go ls rs
            go [] rs = map (spaces wx ++) rs
            go ls [] = map (++ spaces wy) ls

t1, t2 :: Tree Int
t1 = Node (Node (Leaf 1) (Leaf 2)) (Node (Leaf 3) (Leaf 4))
t2 = Node t1 (Node (Node (Leaf 5) (Leaf 6)) (Node (Leaf 7) (Leaf 8)))

main :: IO ()
main = do
  pprint t1
  pprint . fromJust $ interleave t1
  pprint . fromJust $ toList &gt;&gt;&gt; rotateR &gt;=&gt; rotateR $ t1