construct bst by preorder

construct_pre_bst.py

3 1 2 6 4 5

        3
    1       6
      2   4
            5

Basic Method:
Use the first element of preorder to divide the problem into 2 sub problems, construct the tree recursively
1. make the first element as root node
2. find the next element that is greater than the first element, say the idx is i
3. construct recursively
    root.left = construct(preorder, start+1, i-1)
    root.right = construct(preorder, i+1, end)
repeat 1,2,3 until start > end

T(n) = 2T(n/2) + O(n) = O(n^2)

Better Method:
if we preapare the next greater element for each element, than :
T(n) = 2T(n/2) + O(1) = O(n)
use next array to store the next greater element for each idx.
maintain a decreasing stack
1. init the next array with n  (last element)
2. iterate through the array
a). push the element into stack if element is smaller than the top element
b). otherwise pop the element, set the next[t] to the current element
3. reapeat 2 until reach to the end of the array

3 1 2 6 4   ||
3 1 | 2     ||     2
3 2 | 6     ||  3  2  3
6 4         ||  3  2  3  5  5
'''

def constructBasic(preorder, start, end):
    # base bad case
    if start > end:
        return None
    i, root = start, TreeNode(preorder[start])
    while i <= start:
        if preorder[i] > preorder[start]:
            break
        i += 1
    root.left = constructBasic(preorder, start+1, i-1)
    root.right = constructBasic(preorder, i, end)
    return root


def constructBetterUtil(preorder, next, start, end):
    if start > end:
        return None
    root = TreeNode(preorder[start])
    i = next[start]
    root.left = constructBetterUtil(preorder, next, start+1, i-1)
    root.right = constructBetterUtil(preorder, next, i, end)
    return root


def constructBetter(preorder):
    i, n, s = 0, len(preorder), []
    next = [n] * n
    while i < n:
        if not s or preorder[i] < preorder[s[-1]]:
            s.append(i)
            i += 1
        else:
            j = s.pop()
            next[j] = i
    return constructBetterUtil(preorder, next, 0, n-1)