# Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex

How to build tree with more than 6 vertices, that after operation splay() would have depth = number of vertices? Is it possible?

UPD: Example for n = 4:

• insert 60
• insert 10
• insert 20
• insert 50
• splay(10)

You can use splay tree visualization

• Are there such examples when the number of vertices is less than or equal to 6? Please show them in the question. – Apass.Jack Dec 23 '18 at 17:50
• @Apass.Jack I added an example for n = 4 – Gleb Dec 23 '18 at 18:14
• Depth should be $n-1$ instead of $n$. By convention, a tree with only a single vertex (hence both a root and leaf) has depth and height zero. – Apass.Jack Dec 24 '18 at 2:14

## 1 Answer

This is a good question whose answer can help us understand how splay tree tends to keep away from being imbalanced.

No, it is impossible for any rooted tree with more than 5 vertices to become a linear tree after operation splay() one of the deepest vertices, i.e. its depth is one less than the number of vertices.

Why?

For the sake of contradiction, let there be a rooted tree with more than 5 vertices which becomes a linear tree after splaying $$x$$, one of its deepest vertices. Consider the point of time just before the last splay step that moves $$x$$ to the root. There are three cases.

• That last step is a zig-step (the following graph) or its mirroring zag-step. Since the resulted tree is linear, part $$A$$ and $$B$$ are empty. That means, the left subtree of the root before that step contains node $$x$$ only. Since $$x$$ is the deepest node, the whole tree has at most 3 nodes, which is not true.

• That last step is zig-zig step (the following graph) or its mirroring zag-zag. Since the resulted tree is linear, part $$A$$, $$B$$ and $$C$$ are empty. That means, the left subtree of the root before that step contains node $$P$$ and $$x$$ only. Part $$D$$ can have at most two nodes; otherwise, either $$x$$ was not the deepest node or the resulted tree is not linear. So the whole tree has at most 5 nodes, which is not true.

• That last step is a zig-zag step (the following graph) or its mirroring zag-zig. However, after that step, the root will alway has two children, which is not ture.

Exercise. Draw a tree with 5 vertices that becomes a linear tree after splaying one of its deepest vertices.