Create a complete binary search tree from list

Question

I am trying to make an algorithm that creates a complete binary search tree given a list of values. Complete, in that all levels are full except for maybe the last level, which needs to have all elements shifted as far left as possible.

I've implemented something (in Python) that will create a balanced BST, like this:

# TreeNode constructor takes (data, left, right, parent)
def make_tree(arr, parent):
    if not arr:
        return None

    length = len(arr)
    if length == 1:
        return TreeNode(arr[0], None, None, parent)
    else:
        mid = int(len(arr)/2)
        mid_node = TreeNode(arr[mid], None, None, parent)
        mid_node.left = make_tree(arr[0:mid], mid_node)
        mid_node.right = make_tree(arr[mid+1:length], mid_node)
        return mid_node

It works by recursively splitting the list by the midpoint, and making the midpoint a parent node.

However, this does not create a complete BST. Given the list [2,4,7,8,10], it will create this:

      7

   /    \ 

  4     10

/       /

2      8

But a complete BST would look like this:

      8

   /    \ 

  4     10

 /  \ 

2    7 

Do you have any suggestions on how to modify my approach to accomplish this?

Answer 1

The construction of a complete BST is similar to the one of a balanced BST. You just have to find the correct middle. I used the following function:

def perfect_tree_partition(n):
    """find the point to partition n keys for a perfect binary tree"""
    x = 1

    # find a power of 2 <= n//2
    # while x <= n//2:  # this loop could probably be written more elegantly :)
    #     x *= 2
    x = 1 << (n.bit_length() - 1)   # indeed you can

    if x//2 - 1 <= (n-x):
        return x - 1      # case 1
    else:
        return n - x//2   # case 2 == n - (x//2 - 1) - 1

There are two cases: Either

• case 1: the left subtree of the root is perfect and the right subtree has less nodes or
• case 2: the left subtree of the root has more nodes and the right subtree is perfect.

In both cases the number of nodes in the perfect subtree is some 2**d - 1 so the root is the 2**dth node counting from the left (case 1) or the right (case 2). You just have to subtract 1 because indexing starts at 0.