 # 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