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:
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))