Binary Search Tree (BST) Array Implementation in Python

bst_array

# Compact BST (Array Implementation) -----------#
# rightPtr = Ptr * 2 + 2, leftPtr = Ptr * 2 + 1 #

BST = [None for _ in range(21)]

def insert(BST, data):
    
    if not BST[0]: # empty
        BST[0] = data
        
    else:
        curr_ptr = 0
        done = False

        while not done:

            if curr_ptr >= 30:
                done = True

            elif not BST[curr_ptr]:
                BST[curr_ptr] = data
                done = True
            
            elif data > BST[curr_ptr]:
                curr_ptr = curr_ptr * 2 + 2
                
            else:
                curr_ptr = curr_ptr * 2 + 1

def in_order_traversal(BST, curr_ptr):

    # left
    left_ptr = curr_ptr * 2 + 1
    if left_ptr < 21 and BST[left_ptr]:
        in_order_traversal(BST, left_ptr)
    
    # print
    print(BST[curr_ptr])
    
    # right
    right_ptr = curr_ptr * 2 + 2
    if right_ptr < 21 and BST[right_ptr]:
        in_order_traversal(BST, right_ptr)

def all_paths_to_leaves(BST):

    result = []

    def helper(curr_ptr, path):

        nonlocal result
        path = path + [BST[curr_ptr]]

        # is leaf
        if (curr_ptr * 2 + 1 < 21 and not BST[curr_ptr * 2 + 1] or curr_ptr * 2 + 1 >= 21)\
            and (curr_ptr * 2 + 2 < 21 and not BST[curr_ptr * 2 + 2] or curr_ptr * 2 + 2 >= 21):
            result.append(path)

        # not leaf
        else:
            if curr_ptr * 2 + 1 < 21 and BST[curr_ptr * 2 + 1]:
                helper(curr_ptr * 2 + 1, path)

            if curr_ptr * 2 + 2 < 21 and BST[curr_ptr * 2 + 2]:
                helper(curr_ptr * 2 + 2, path)

    helper(0, [])
    return result

def test():
    for num in [51, 30, 10, 78, 34, 36, 31, 32, 15, 3, 91, 93, 80]:
        insert(BST, num)
    print(BST)
    in_order_traversal(BST, 0)
    print(all_paths_to_leaves(BST))