Cracking the Coding Interview 4.1 Balanced Tree

As decided, here I am in the bus solving the first exercise from the Trees&Graphs chapter of the Cracking the codining initerview book.
It sounds like this:

4.1 Implement a function to check if a tree is balanced. For the purposes of this question,
a balanced tree is defined to be a tree such that no two leaf nodes differ in distance
from the root by more than one.

First representation – the TreeNode class

First thing we’ll have to decide is a representation of our tree. My first attempt is to write a class for a tree node.
Here it is:

class TreeNode(object):
	def __init__(self,data,children=None):
		self.data=data
		if children is None:
			self.children=[]
		else:
			self.children=children
		def addChild(self, node):
			self.children.append(child)

		def show(self,level=0):
			print level*"          " + self.data
			for child in self.children:
				child.show(level+1)

Now, let’s write the isBalanced method, and some tests.
Here’s the method (we still ned to write the minDepth and maxDepth functions):

def isBalanced(n):
	return maxDepth(n) - minDepth(n) < 2

Let’s take a sample tree (I used http://www.diagram.ly to draw it). I drew a binary tree but it should work just fine with any type of tree.

And here is my test:

	
def test():
	n1 = TreeNode("1")
	n2 = TreeNode("2")	
	n3 = TreeNode("3",[n1,n2])
	n4 = TreeNode("4")
	n5 = TreeNode("5",[n4])
	n6 = TreeNode("6",[n5])
	n7 = TreeNode("7",[n6,n3])
#	n7.show()
	assert(minDepth(n7)==3)
	assert(maxDepth(n7)==4)
	assert(isBalanced(n7))
	assert(minDepth(n6)==3)
	assert(maxDepth(n6)==3)
	assert(isBalanced(n6))

if __name__=='__main__':
	test()

All we need to do is to write the recursive functions minDepth and MaxDepth. Here they are:

def minDepth(n):
	if n.children==[]:
       		return 1
	return  1+ min (minDepth(x) for x in n.children)

def maxDepth(n):
	if n.children==[]:
       		return 1
	return  1+ max (maxDepth(x) for x in n.children)

Well this is it. My office collegue and blog reader, Sergei, did not like it. He sais its too verbose and too complicate to create trees for the purpose of the exercise. He advises me to represent the tree a list.

Second representation – a list of lists

So I decided to represent a node as a list: the first element will be the data, while the next elements will be lists representing the children nodes. So, I can write a tree in a single line like:

myTree=["root",["leafAtLevel1"],["nodeAtLevel1",["leafAtLevel2"]],["anotherNodeAtLevel1"]]

So let’s write my tree example from above. Let’ build it first, as we did with the TreeNode class.

	n1=["1"]
	n2=["2"]
	n3=["3",n1,n2]
	n4=["4"]
	n5=["5",n4]
	n6=["6",n5]
	n7=["7",n6,n3]

This could also be written as

       n7 = ['7', ['6', ['5', ['4']]], ['3', ['1'], ['2']]]

My asserions remain the same. I only need to update the minDepth and maxDepth functions. Here is the full code:


def minDepth2(n):
	if len(n)==1:
		return 1
	return 1 + min(minDepth2(x) for x in n[1:len(n)])

def maxDepth2(n):
	if len(n)==1:
		return 1
	return 1 + max(maxDepth2(x) for x in n[1:len(n)])

def isBalanced2(n):
	return maxDepth2(n) - minDepth2(n) < 2
	
def test():
	n7=['n7', ['n6', ['n5', ['n4']]], ['n3', ['n1'], ['n2']]]
	assert(minDepth2(n7)==3)
	assert(maxDepth2(n7)==4)
	assert(isBalanced2(n7))
	assert(minDepth2(n6)==3)
	assert(maxDepth2(n6)==3)
	assert(isBalanced2(n6))
Advertisements
This entry was posted in Cracking the coding interview - a python experience. Bookmark the permalink.

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