Create a complete binary search tree from a list

Question

I am trying to create an algorithm that creates a complete binary search tree, given a list of values. Complete that all levels are complete, with the possible exception of the last level, which should have all the elements shifted as far as possible.

I implemented something (in Python) that would create a balanced BST, for example:

# 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 breaking the list by midpoint and making the middle the parent node.

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

  7 / \ 4 10 / / 2 8 

But the full BST will look like this:

  8 / \ 4 10 / \ 2 7 

Do you have any suggestions on how to change my approach to achieve this?

Answer 1

Building a complete BST is similar to building a balanced BST. You just need to find the right 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 <= (nx): 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 fewer nodes or
• case 2: the left subtree of the root has more nodes and the correct subtree is ideal.

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

Answer 2

If this is just a one-time operation, you can sort the list first and then build a BST. This makes the problem trivial.