figure two leftist heaps and figure result of merging with ' right subheap reasonable to assume that the resulting tree is leftist heapbecause it was obtained via recursive step this is much like the inductive hypothesis in proof by induction since we can handle the base case (which occurs when one tree is empty)we can assume that the recursive step works as long as we can finish the mergethis is rule of recursionwhich we discussed in we now make this new heap the right child of the root of (see fig although the resulting heap satisfies the heap-order propertyit is not leftist because the left subtree of the root has null path length of whereas the right subtree has null path length of thusthe leftist property is violated at the root howeverit is easy to see that the remainder of the tree must be leftist the right subtree of the root is leftist because of the recursive step the left subtree of the root has not been changedso it too must still be leftist thuswe need only to fix the root we can make the entire tree leftist by merely swapping the root' left and right children (fig and updating the null path length-the new null path length is plus the null path length of the new right child--completing