Write method levelOrder to perform a level-order traversal of a binary tree object. Modify the program of Fig. 22.16 to use this function.

Question

The program of Fig. 22.16 illustrated three recursive methods of traversing a binary tree—inorder, preorder and postorder traversals. This exercise pre-
sents the level-order traversal of a binary tree in which the node values are printed level by level, starting at the root node level. The nodes on each level are printed from left to right. The level-order traversal is not a recursive algorithm. It uses a Python built-in list object to control the output of the nodes. The algorithm is as follows:
1) Insert the root node in the list
2) While there are nodes left in the list,
Get the next node in the list
Print the node’s value
If the reference to the left child of the node is not None
Insert the left child node in the list
If the reference to the right child of the node is not None
Insert the right child node in the list.

Answer 1

```
# Tree definition with level-order traversal.

class Treenode:
"""Single Node in a Tree"""

def __init__( self, data ):
"""Treenode constructor"""

self._left = None
self._data = data
self._right = None

def __str__( self ):
"""Tree string representation"""

return str( self._data )

class Tree:
"""Binary search tree"""

def __init__( self ):
"""Tree Constructor"""

self._rootNode = None

def insertNode( self, value ):
"""Insert node into tree"""

if self._rootNode is None: # tree is empty
self._rootNode = Treenode( value )
else: # tree is not empty
self.insertNodeHelper( self._rootNode, value )

def insertNodeHelper( self, node, value ):
"""Recursive helper method"""

if value < node._data: # insert to left

if node._left is None:
node._left = Treenode( value )
else:
self.insertNodeHelper ( node._left, value )

elif value > node._data:

if node._right is None: # insert to right
node._right = Treenode( value )
else:
self.insertNodeHelper( node._right, value )

else: # duplicate node
print value, "duplicate"

def preOrderTraversal( self ):
"""Preorder traversal"""

self.preOrderHelper( self._rootNode )

def preOrderHelper( self, node ):
"""Preorder traversal helper function"""

if node is not None:
print node,
self.preOrderHelper( node._left )
self.preOrderHelper( node._right )

def inOrderTraversal( self ):
"""Inorder traversal"""

self.inOrderHelper( self._rootNode )

def inOrderHelper( self, node ):
"""Inorder traversal helper function"""

if node is not None:
self.inOrderHelper( node._left )
print node,
self.inOrderHelper( node._right )

def postOrderTraversal( self ):
"""Postorder traversal"""

self.postOrderHelper( self._rootNode )

def postOrderHelper( self, node ):
"""Postorder traversal helper function"""

if node is not None:
self.postOrderHelper( node._left )
self.postOrderHelper( node._right )
print node,

def levelOrder( self ):
"""Level-order traversal"""

treeNodes = []

# insert root node
treeNodes.append( self._rootNode )

# while the list is not empty
while len( treeNodes ):

# get next node in list and print its value
node = treeNodes.pop( 0 )
print node._data,

# insert left child node in list if it is not None
if node._left != None:
treeNodes.append( node._left )

# insert right child node in list if it is not None
if node._right != None:
treeNodes.append( node._right )
```
```
# The driver to demonstrate level-order binary tree traversal.

from TreeModule import Tree

tree = Tree()

values = raw_input( "Enter 10 integer values:\n" )

for i in values.split():
tree.insertNode( int( i ) )

print "Level-order Traversal"
tree.levelOrder()
print
```
Enter 10 integer values:
8 4 5 1 2 16 9 3 11 19
Level-order Traversal
8 4 16 1 5 9 19 2 11 3