Question

What would be the result if the left subtree of the root has a null path length of 1 and the right subtree has a null path length of 2?

(a) merge occurs without violation

(b) violation at left subtree

(c) violation at right subtree

(d) violation at the root

My question comes from Heap in chapter Heap of Data Structures & Algorithms I

I got this question during an interview.

Answer 1

Correct answer is (d) violation at the root

To explain: When two leftist heaps are merged, if the left subtree of the root has a null path length of 1 and the right subtree has a null path length of 2, leftist property is violated at the root.