Cracking the coding interview in python – 4.3 binary tree from list

Today’s exercise is simple. A binary tree, a list and a recursive call.

Here it is:

4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree with
minimal height.

I think she actually means a binary search tree.

The solution in the book makes recursion calls and give as argument the indexes in the array for the portion that is to be treated on the curent call: TreeNode addToTree(int arr[], int start, int end).
What if we used python notation arrray[x:y] instead of passing indexes ?

My function becomes:

def create_tree(array):
	if (array==[]):
		return None
	mid = (len(array))/2
	node = TreeNode(array[mid])
	node.left = create_tree(array[0:mid])
	node.right = create_tree(array[mid+1:])
	return node

I will write a representation of the tree in my next post. This is it for today.

Update – let’s make it more pythonic

by taking into account mebubo ‘s comments:

def create_tree(array):
	if not array:
		return
	mid = (len(array))/2
	node = TreeNode(array[mid])
	node.left = create_tree(array[:mid])
	node.right = create_tree(array[mid+1:])
	return node
Advertisements
This entry was posted in Cracking the coding interview - a python experience. Bookmark the permalink.

2 Responses to Cracking the coding interview in python – 4.3 binary tree from list

  1. mebubobo says:

    Again, more pythonic would be to write

    if not array:
    return

    Also, you don’t need to specify the starting index if it is zero:

    array[0:mid] == array[:mid]

  2. Denis Akulov says:

    mid = (len(array))/2
    Can be:
    mid = len(array) / 2

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s