Cartesian Tree Parent Array

Problem

Build the Cartesian tree of nums, a min-heap-by-value tree whose inorder traversal is nums. Equal values keep the left occurrence above the right one, as produced by a monotonic stack that pops while the stack top is strictly greater than the current value. Return the parent array with -1 at the root. An empty array returns [].

Hint

The stack holds the right spine of the tree built so far; popped nodes become the left subtree of the current node.

Test cases

case 1

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

expected: [1,-1,3,1]

case 2

in: [[1,2,3]]

expected: [-1,0,1]

case 3

in: [[3,2,1]]

expected: [1,2,-1]

case 4

in: [[2,2,1]]

expected: [2,0,-1]

case 5

in: [[5]]

expected: [-1]

Starter codePython

def cartesian_parent(nums):
    # Your code here
    pass

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