Extracting the Root of a Leftist Tree A leftist tree is a variant of a binary heap, where the height of the left side of the tree is usually greater than the right side. Can a leftist tree's height ever increase after extracting the root? I am pretty sure it is impossible. How can a tree's height increase after taking away a node?
When extracting the root, the subtrees of the root remain and have to merged. Merging two leftist trees is done by "zipping" the trees along their rightmost paths. Two short paths together might be rather long. Try some examples.