Good morning! Here's your coding interview problem for today.
This problem was asked by Netflix.
A Cartesian tree with sequence S is a binary tree defined by the following two properties:
- It is heap-ordered, so that each parent value is strictly less than that of its children.
- An in-order traversal of the tree produces nodes with values that correspond exactly to S.
For example, given the sequence [3, 2, 6, 1, 9], the resulting Cartesian tree would be:
1
/ \
2 9
/
3 6
Given a sequence S, construct the corresponding Cartesian tree.