A complete binary search tree is a complete binary tree that satisfies the left-right ordering property of binary search tree as well as the structure of a complete binary tree. Since a complete binary tree can be perfectly stored in an array, we can also store the complete BST in an array. In this lab, you will be given an array of integers as input. The objective is to write a function to_bst(lst) to convert the array to a complete binary tree that stores in an array with the same length. For example, given an array [29, 72, 1, 34, 22], the corresponding complete BST is [34, 22, 72, 1, 29]. Hint: Consider the inorder traversal of the BST. For example: Test Result keys = [29, 72, 1, 34, 22] to_bst(keys) print(keys)

Here is a Python implementation of the to_bst(lst) function:

def to_bst(lst):
    # Sort the input list
    lst.sort()
    # Create an empty BST array with the same length as lst
    bst = [None] * len(lst)
    # Recursively fill the BST array using inorder traversal
    def fill_bst(start, end, idx):
        if start > end:
            return
        mid = (start + end) // 2
        bst[idx] = lst[mid]
        fill_bst(start, mid-1, 2*idx+1)
        fill_bst(mid+1, end, 2*idx+2)
    fill_bst(0, len(lst)-1, 0)
    return bst

The implementation first sorts the input list in ascending order to satisfy the left-right ordering property of binary search tree. Then it creates an empty BST array with the same length as the input list. The fill_bst function recursively fills the BST array using inorder traversal. At each recursive call, it finds the middle element of the current range (start to end) and assigns it to the current index of the BST array. Then it recursively fills the left subtree with the elements before the middle element and the right subtree with the elements after the middle element. The left child of a node at index i is at index 2*i+1 and the right child is at index 2*i+2.

To test the implementation, we can use the provided example:

keys = [29, 72, 1, 34, 22]
bst = to_bst(keys)
print(bst)  # Output: [34, 22, 72, 1, 29]

The output shows that the input list has been converted to a complete BST array with the same length.