Under the assumption that a leftist tree has m internal nodes, where x is the label of the root and s(x) is its s-value (just give a sketch of the proof).

 

Show that,

a             s(x) ≤ log₂ (m + 1) 

 

  b.  The right most branch of the leftist tree is of length s(x).