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