2
$\begingroup$

I am working on this project where I am required to find the theoretical proof for following.

I have a particular type of binary trees, where

1) each internal node will definitely have two children.

2) There are n leaf nodes and can be assumed in order 1 to n from left most to right most.

Now this is clear that there are multiple such trees. And I am performing tree rotation (https://en.wikipedia.org/wiki/Tree_rotation) operation in any of one internal node of the tree.

I was thinking that in any such type of tree with n leaf nodes there will be guaranteed n-1 internal nodes and total n-2 possible rotation moves. (The rotation is only valid if the rotated tree also has the two given properties i.e. an internal node with just left node as leaf node cannot be right rotated.)

I have tried various resources but couldn't find any proof for it. I have tried it myself but not able to reach to a solution. I'd be glad if someone can help me out here.

EDIT:

I could get to one possible proof, please see if it's correct.

There are 3 parts of the proof:

a) With these rotation moves, you can convert to any of the tree into a completely left branching tree, I have the proof for it and it's well known in graph theory.

b) Any rotation moves preserves the number of possible rotations in the tree. This is critical, I will prove it in the end.

c) In any left branching tree, out of total n-1 internal node, everyone except one can be right rotated. So total n-2 rotations.

All 3 together gives that total n-2 rotations possible.

Now the critical (b) part:

From the wikipedia image on the link (https://en.wikipedia.org/wiki/Tree_rotation), the number of rotations for subtrees A, B ,C remains the same and reverses for P and Q. So the total moves will remain same.

I can give more details for the above statement if required, but it's hard to write it here.

$\endgroup$
  • 1
    $\begingroup$ Have you tried some small(ish) examples by hand? Have you tried to find a tree that doesn't comply? (The last, if it fails, may point you to why it does always work out; iif it succeeds, it provides a counterexample and perhaps a different bound.) $\endgroup$ – vonbrand Oct 14 '15 at 21:35
  • $\begingroup$ @vonbrand I have tried and definitely couldn't find a counterexample. In fact in the meanwhile, I guess I found some proof (not sure if it's correct) but not sure about the correctness. $\endgroup$ – Naman Oct 14 '15 at 22:20
  • $\begingroup$ You should certainly give your proof here (edit your question to add it), others might see flaws (and ways to fix them). $\endgroup$ – vonbrand Oct 14 '15 at 23:23
  • $\begingroup$ @vonbrand I added it, please let me know what you think of it? $\endgroup$ – Naman Oct 15 '15 at 0:26
3
$\begingroup$

Each rotation involves a node and its left or right child. We can associate this rotation with the child – the rotation is fixed once the child is known. In your case, a child can be rotated as long as it is an internal node. So the number of possible rotations is the number of non-root internal nodes. A simple induction shows that a full binary tree having $n$ leaves has exactly $n-1$ internal nodes, and so $n-2$ non-root internal nodes.

$\endgroup$
  • 1
    $\begingroup$ True, your proof seems much straight forward than mine. $\endgroup$ – Naman Oct 15 '15 at 17:59

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.