You are implementing a weight-balanced binary search tree where you guarantee that at every node of the binary search tree, the size of the left subtree is less than or equal to twice the size of the right subtree, and vice versa. Let us define size( x ) to be the number of nodes in the subtree rooted at node x (including x). Then the condition that you are guaranteeing is that for all nodes x in T, size( xL ) 2 size( xR ) and size( xR ) 2 size( xL ) where xL and xR are, respectively, the left and right child of x.

Prove by induction on n that LazyBSTs are also height balanced by showing that every subtree in a LazyBST with n nodes has height less than or equal to 3 log n.