Creating a balanced BST in Python

Question

I'm trying a implement a complete BST tree, currently I have only created a balanced tree. The idea is to move all the leaves from the balance tree to the left of the left subtree to create a complete BST tree but I can't adjust the leaves correctly.

This is what the function for sorting a sorted array for the BST tree looks like

def test(sorted_numbers):
    bst = BST()
    array = []
    test_sort(sorted_numbers, bst, array)
    print("Array from Constructed Balanced BST:", array)
    return bst

def test_sort(sorted_numbers, bst, array):
    def sort(start, end):
        if start > end:
            return None
        if start == 0 and end == len(sorted_numbers) - 1:
            mid = (start + end) // 2  
            mid = min(mid + 3, len(sorted_numbers) - 1) 
        else:
            mid = (start + end + 1) // 2 
        mid_value = sorted_numbers[mid]
        bst.insert(mid_value)
        array.append(mid_value)
        sort(start, mid - 1)
        sort(mid + 1, end)
    sort(0, len(sorted_numbers) - 1)

And here is the Tree and BST class if needed.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(val, self.root)

    def _insert(self, val, node):
        if val < node.val:
            if node.left:
                self._insert(val, node.left)
            else:
                node.left = TreeNode(val)
        else:
            if node.right:
                self._insert(val, node.right)
            else:
                node.right = TreeNode(val)

    def inorder(self):
        self._inorder(self.root)
        print()

    def _inorder(self, node):
        if node:
            self._inorder(node.left)
            print(node.val, end=' ')
            self._inorder(node.right)

    def preorder(self):
        self._preorder(self.root)
        print()

    def _preorder(self, node):
        if node:
            print(node.val, end=' ')
            self._preorder(node.left)
            self._preorder(node.right)

    def postorder(self):
        self._postorder(self.root)
        print()

    def _postorder(self, node):
        if node:
            self._postorder(node.left)
            self._postorder(node.right)
            print(node.val, end=' ')

The code exports:

                 __________65_______
                /                   \
           ____34_____           __84___
          /           \         /       \
        _14___       49___     80_     99_
       /      \     /     \   /   \   /   \
       0     21    46    57  66  82  90  132
      / \   /     /     /
     -8 9  18    45    55

Node 21, 46 and 57 are missing a child, I have only managed to shift the "leaves" to the left subtree but haven't created a complete binary tree.

So what I want should look something like this as a complete tree

                 __________65_______
                /                   \
           ____34_____           __84___
          /           \         /       \
        _14___       49___     80_     99_
       /      \     /     \   /   \   /   \
       0     21    46    57  66  82  90  132
      / \   /  \   / \    
     -8 9  18  23 45  47                    (just an example of the shape I want)

Any guidance on how to achieve this tree would be appreciated.

Answer 1

You need to calculate the mid index differently. Note how only the size of the left subtree influences this mid index. If the left subtree is full, this index does not change when one more leaf is added to the not-full right subtree.

So the formula for mid is a bit more complex than what you had foreseen.

Replace this piece of code:

        if start == 0 and end == len(sorted_numbers) - 1:
            mid = (start + end) // 2  
            mid = min(mid + 3, len(sorted_numbers) - 1) 
        else:
            mid = (start + end + 1) // 2 

with this:

        size = end + 1 - start  # Number of nodes in this (sub)tree
        # Derive maximum number of leaves possible with this height (perfect tree):
        fullbottom = 1 << (size.bit_length() - 1)
        # Get actual number of leaves in bottom level (complete tree):
        actualbottom = size - (fullbottom - 1)  
        mid = start + fullbottom // 2 + min(actualbottom, (fullbottom + 1) // 2) - 1

Note that calling insert repeatedly like that you don't achieve the optimal time complexity. It is O(𝑛log𝑛). Building a BST from an already sorted list can be done with O(𝑛) time complexity. You could still use recursion, but instead of calling insert, you'd create a single node and attach the nodes you get from two recursive calls as children.

The toplevel call would assign the returned node to its BST root.

Here is how that could look (I left out the array part):

def test_sort(sorted_numbers):
    def sort(start, end):
        if start > end:
            return None
        size = end + 1 - start  # Number of nodes in this (sub)tree
        # Derive maximum number of leaves possible with this height (perfect tree):
        fullbottom = 1 << (size.bit_length() - 1) 
        # Get actual number of leaves in bottom level (complete tree):
        actualbottom = size - (fullbottom - 1)  
        mid = start + fullbottom // 2 + min(actualbottom, (fullbottom + 1) // 2) - 1
        mid_value = sorted_numbers[mid]
        return TreeNode(mid_value, sort(start, mid - 1), sort(mid + 1, end))

    bst = BST()
    bst.root = sort(0, len(sorted_numbers) - 1)
    return bst

Call as:

bst = test_sort(sorted_numbers)