Sunday, August 07, 2016

construct bst from sorted array

If array has dupes then mid has to adjusted to rightmost dupe as left subtree <= node < right subtree for bst.
0123456
s  m  e
sme

01234
s m e
se
m

111
s e
 -m

11
se
-m
atobst(a):
    if a == null:
        throw
    return atobst(a, 0, a.length()-1)

// a is asc
atobst(a, start, end):
    if start > end:
        return null
    mid = start + (end-start)/2
    while mid < end && a[mid] == a[mid+1]
        mid++
    n = new node(a[mid])
    n.left = atobst(a, start, mid-1)
    n.right = atobst(a, mid+1, end)
    return n

// a is desc
atobst(a, start, end):
    if start > end:
        return null
    mid = start + (end-start)/2
    while mid > start && a[mid] == a[mid-1]
        mid--
    n = new node(a[mid])
    n.left = atobst(a, mid+1, end)
    n.right = atobst(a, start, mid-1)
    return n
[Hat tip to MA]

No comments:

Post a Comment