Skew Heap Merge Lite

Problem

Merge two skew heaps and return the resulting binary tree.

A node is [value, left, right] and None is an empty heap. Recursively merge: keep the smaller root, merge its right child with the other heap, then swap the node's children.

Return the merged tree in node-list form.

Hint

The unconditional swap keeps the amortized cost logarithmic.

Test cases

case 1

in: [[1,[4,null,null],[5,null,null]],[2,[3,null,null],null]]

expected: [1,[2,[5,null,null],[3,null,null]],[4,null,null]]

case 2

in: [[5,null,null],[3,null,null]]

expected: [3,[5,null,null],null]

case 3

in: [null,[1,null,null]]

expected: [1,null,null]

case 4

in: [[2,null,null],[2,null,null]]

expected: [2,[2,null,null],null]

Starter codePython

def skew_merge(a, b):
    # Your code here
    pass

4 test cases · run your code against them in the editor