Inorder Traversal of Cartesian Tree

Given an inorder traversal of a cartesian tree, construct the tree.

Cartesian tree : is a heap ordered binary tree, where the root is greater than all the elements in the subtree.

Note: You may assume that duplicates do not exist in the tree.

Example :

Input : [1 2 3]

Return :   
          3
         /
        2
       /
      1
Interview Code Editor
Hints
  • Solution Approach
  • Complete Solution
3594 successful submissions.
Asked In:
  • Amazon
Click here to jump start your coding interview preparation