In [ ]:
Implement a program that lists the nodes of a random binary tree by nodes at the same depth.
This problem is commonly termed 'Level order traversal of a binary tree'.
One common approach uses a Breadth First Search algorith, while tracking the nodes at each level.
Here is a TreeNode class to use. Not part of the question, but useful for implmentation and later testing.
In [8]:
class BinaryTree(object):
def __init__(self,rootObj):
self.key = rootObj
self.leftChild = None
self.rightChild = None
def insertLeft(self,newNode):
if self.leftChild == None:
self.leftChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.leftChild = self.leftChild
self.leftChild = t
def insertRight(self,newNode):
if self.rightChild == None:
self.rightChild = BinaryTree(newNode)
else:
t = BinaryTree(newNode)
t.rightChild = self.rightChild
self.rightChild = t
def getRightChild(self):
return self.rightChild
def getLeftChild(self):
return self.leftChild
def setRootVal(self,obj):
self.key = obj
def getRootVal(self):
return self.key
In order to print the binary tree in level order with newline in the end of each level, we can utilize two queues. The first queue stores the current level’s nodes, while the second queue stores the next level’s nodes (the current level nodes’ children).
When the first queue is emptied, we know that it must have reached the end of the current level, therefore we print a newline. Then, we switch the emptied first queue with the second queue (which is populated with the next level’s nodes). Then we repeat the process over again.
In [28]:
def level_order_traversal(node):
"""
head: The root node of a TreeNode class to be searched.
"""
# Edge case: Check if initial node is a root.
if (node.leftChild==node.rightChild==None):
print "node passed in has no children!"
return repr(node.key)
# Use 2 lists as the current and next level queues
currLvl = []
nextLvl = []
outstr = ''
# Load up current level queue with head/root node passed in
currLvl.append(node)
# Iterate through until the current level is empty
while len(currLvl)>0:
# pop off front of the queue
currNode = currLvl.pop(0)
if currNode != None:
# current node exists, so add its value to the str
# and add its children to next level
outstr += str(currNode.key)+" "
nextLvl.append(currNode.leftChild)
nextLvl.append(currNode.rightChild)
if len(currLvl)==0:
# current level queue is empty
# So, add end of line to str, and swap next for current queue
outstr += "\n"
currLvl = nextLvl
nextLvl = []
return outstr
In [29]:
book = BinaryTree('book')
# load up chapter 1 on left
book.insertLeft('Chapter 1')
book.getLeftChild().insertLeft("Section 1.1")
s12 = BinaryTree('Section 1.2')
s12.insertLeft("Section 1.2.1")
s12.insertRight("Section 1.2.2")
book.getLeftChild().rightChild = s12
# load up chapter 2 on right
book.insertRight("Chapter 2")
book.getRightChild().insertLeft("Section 2.1")
s22 = BinaryTree('Section 2.2')
s22.insertLeft("Section 2.2.1")
s22.insertRight("Section 2.2.2")
book.getRightChild().rightChild = s22
In [31]:
a = level_order_traversal(book)
print a
'method 1' from here Uses a helper function that is recursive.
In [169]:
def level_order_traversal2(node):
# perform edge case checks (Skipped for now)
outstr = ""
h = height(node)
#print h
for i in range(1,h+1):
print 'level ',i
#print outstr
outstr = print_given_level(node,i,outstr)
#print
print outstr
#outstr += "\n"
return outstr
# Make the helper function
def print_given_level(node,level,outstr):
#print repr(node.key)
#print repr(outstr)
if (node is None) or (node.key is None):
# this is pointing past/from a leaf, nothing to do
#if outstr is None:
# outstr = ''
return outstr
if level == 1:
# at a leaf, add node value to string
#print repr(outstr)
#if outstr is None:
# outstr = ''
outstr += repr(node.key)
#return outstr
#outstr += repr(node.key)
#return outstr
elif level > 1:
# above a leaf, recurse down one more level
outstr = print_given_level(node.leftChild,level-1,outstr)
outstr = print_given_level(node.rightChild,level-1,outstr)
# helper function 2, find the height of the tree
def height(node):
if node is None:
return 0
else:
lheight = height(node.leftChild)
rheight = height(node.rightChild)
return max(lheight,rheight)+1
In [170]:
a = level_order_traversal2(book)
print a
Imagine you are playing a board game. You roll a 6-faced dice and move forward the same number of spaces that you rolled. If the finishing point is “n” spaces away from the starting point, please implement a program that calculates how many possible ways are there to arrive exactly at the finishing point.
If n=610, how many possible ways are there to arrive exactly at the finishing point?
In [ ]:
In [ ]: