# Facebook | Phone Screen | Q2

Hi guys,
This is a second problem of the week. The problem is to implement a Cartesian Tree given an array. You can find the problem here.
Problem statement:
Input: Array of integers
Output: A tree that has 3 property:

1. Binary Tree
2. Min tree (heap)
3. In order traversal return original array.

For this problem, there can be 2 approaches:

1. Construct such tree while iterate through the array
2. Use a variant of segment tree, that store min value of a given range and the index of this min value. Using this segment tree, we can generate our Cartesian tree
First Approach
class TreeNode:
def __init__(self,val,left=None,right = None):
self.val = val
self.left = left
self.right = right
class cartersianTree:
def __init__(self,arr):
self.root = self.initialize(arr)

def initialize(self,arr):
root = None
for item in arr:
newNode = TreeNode(item)
if not root:
root = newNode
else:
if newNode.val>root.val:
# make our root as newNode child, set newNode as root
newNode.left = root
root = newNode
# bigger will be lower, and something happens first will be on the left child
else:
# we traverse the right until we hit nothing, or we hit one that is greater than root
# use a copy of the root
tempRoot = root
while tempRoot.right:
# we have to check if our root.right is still lower than item
if tempRoot.right.val<item:
tempRoot= tempRoot.right
else:
# we have to swap
temp = tempRoot.right
tempRoot.right = newNode
newNode.left = temp
break
# we break the loop either we hit none or we have done assignment, if we have done
# asssignment , our tempRoot.right would not be empty
if not tempRoot.right:
tempRoot.right = newNode
return root
Second Approach

Here, I only share the implementation of segment tree to query the minimum value and its index given a range query from i to j

class segmentNode:
def __init__(self,val,start,stop,left=None,right=None):
self.start = start
self.stop  = stop
self.val   = val
self.left  = left
self.right = right

class segmentTree:
def __init__(self,arr):
self.root = self.initialize(arr,0,len(arr)-1)
def initialize(self,nums,start,stop):
if start == stop:
node = segmentNode(nums[start],start,stop)
return node
elif start<stop:
mid = (start+stop)//2
left = self.initialize(nums,start,mid)
right = self.initialize(nums,mid+1,stop)
node  = segmentNode(left.val+right.val,start,stop,left,right)
return node
def getMin(self,i,j):
root = self.root
def dfs(root,i,j):
start,stop = root.start,root.stop
if i== start and j == stop:
return root.val,start
else:
mid = (start+stop)//2
val = 0
# check if i>mid
if i>mid:
val,index = dfs(root.right,i,j)
elif i<=mid:
if j<=mid:
val,index =dfs(root.left,i,j)
else:
# this means we have to search bothway
minLeft,indexLeft  = dfs(root.left,i,mid)
minRight,indexRight = dfs(root.right,mid+1,j)
if minLeft<= minRight:
val,index = minLeft,indexLeft
else:
val,index = minRight,indexRight
return val,index
return dfs(root,i,j)

The time complexity for both approach is O(nlogn). However, for second approach, since we have to build the segment tree, we used O(nlogn) compare to O(n) from first approach. I think an extension question is how to use the second approach to support update function for our cartesian tree in O(nlogn). Please let me know if there is anything wrong, and I would really appreciate any advice. Thank you all