Consider binary trees with some abstract values at the leaves. A tree t2 is said to be "derivable" from a tree t1 iff the set of values in the leaves of t2 is included in the set of values in the leaves of t1. In particular, some values can be removed and some can be duplicated.

I'm looking for a minimal set of somewhat "natural" operations on binary trees that can be composed to transform a tree into any of its derivable trees.

By natural I mean operations which are local to the root of the tree or its vicinity, happen in constant time, and can be somewhat visualized.

For instance, swapping the left and right subtree of the root of performing AVL like rotations would qualify as natural operations.

  • 1
    $\begingroup$ Is a tree with a hundred nodes all labeled "2" considered to be "derivable" from a single node labeled "2"? (Strictly speaking this fits the definition given.) $\endgroup$ – Daniel McLaury Feb 13 at 13:45
  • 1
    $\begingroup$ Another question: does "delete the root node, provided there's no left subtree" count as a "natural" operation? If not, can you give an example of a "natural" operation that deletes a node? $\endgroup$ – Daniel McLaury Feb 13 at 13:54
  • $\begingroup$ Yes, 100 labelled 2 is derivable. Yes, delete the root node provides there's no left subtree is "natural" $\endgroup$ – Arthur B Feb 13 at 17:51

I don't have a proof but I would consider these operations:

  • tree rotations (as in AVL trees / red-black trees)
  • removing a leaf
  • duplication: replacing a leaf $x$ by a node having two leaf children $x$
  • swapping: if a node has two leaf subtrees, swap them

My conjecture is: using tree rotations you can transform the tree into any other tree which has the same leaves, taken according to the in-order visit. E.g. the tree $(1,(2,3))$ can be rotated into $((1,2),3)$, which has the same in-order visit $1,2,3$.

If that holds, we need swaps (at least on the leaves, if not of general subtrees) so to generate all the possible leaves permutations. Alternatively, we could also take any subset of the permutation group which generates the whole group: one might check out an abstract algebra book to find a few example.

After that, leaf removal and duplication can be added so to get the wanted relation.

Again, this needs to be proved carefully -- the above one is only an intuition.

  • $\begingroup$ It doesn't seem like the operations you're defining are local to the root $\endgroup$ – Arthur B Feb 14 at 22:01
  • $\begingroup$ @ArthurB Ah, right. I only read that as "local". I think one might work only on the root by using something similar to "zippers" in functional programming, if you allow the root to have 3 pointers (left child, parent, right child). Essentially, a zipper allows one to "move" around the tree by making the node you visit the new root. This uses only root-local moves. $\endgroup$ – chi Feb 14 at 22:12
  • $\begingroup$ I agree that something like a zipper is probably part of the solution, but the constraint is to work with a binary tree. $\endgroup$ – Arthur B Feb 16 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.