I'm preparing for an exam about Trees. One of the questions that appear in Mark Allen Weiss' "Data Structures and Algorithms Analysis in C++" is:
Prove by induction that if all nodes in a splay tree is accessed in sequential order, the resulting tree consists of a chain of left children.
When I take a set a set of numbers like 5,1,3,6,2,4
and put them into a Splay tree, and then access them all sequentially (1,2,3,4,5,6)
, it is very easy to see that the question statement is indeed true (This is a great visualizer) . I just can't find a way to write it in a proof by induction. Any help would be greatly appreciated as I am a struggling beginner.