Given a sorted list of numbers a, write a function balanced_bst(a) to create a balanced binary search tree. A balanced Binary Search Tree has no more than one level of depth difference between the right and left sides of the tree.

Each value in the list a should correspond to a node value. The return value of balanced_bst() will be the root node of the balanced tree. An empty array passed to balanced_bst() should return None.

For example, given a list a = [1,2,3,4,5,6,7,8], you want to create a balanced tree that may resemble the following:

     /   \
    3     7
   / \   / \
  2   4 6   8

The above figure represents a balanced tree because there is at most 1 level of difference between the depths of each side of the tree.

For this challenge you are given the class TreeNode with the members:

  • value: the node value
  • left: the left child node; defaults to None
  • right: the right child node; defaults to None

The __str__() function is also implemented in the class TreeNode, so at any time you can print the root node to see a basic representation of the tree.

This challenge and variations of it were reported to have been asked at interviews with Google. If you’ve covered the material in Pass the Technical Interview with Python or an equivalent, you should be able to solve this challenge. If you have trouble, try refreshing your knowledge there first.