$4\mathrm{.}29$ a$.$ Show that if all nodes in a splay tree are accessed in sequential order, the resulting tree consists of a chain of left children.

Figure $4\mathrm{.}76$ Tree for Exercise $4\mathrm{.}27$

$186$

Chapter $4$ Trees

$**$ b$.$ Show that if all nodes in a splay tree are accessed in sequential order, then the total access time is $O(N),$ regardless of the initial tree.