Implementation of binary tree traversal

Question

Based on what i understood of Binary Tree, queue and recursion I implemented this Breadth First Search algorithm as follows. Do you have any suggestions to improve (in term of readability, good practice etc...) it?

# Definition for a binary tree node.
class Node(object):
 def __init__(self, val=0, left=None, right=None):
 self.val = val
 self.left = left
 self.right = right
 
 def preorder_print(self):
 print(self.val)
 if self.left:
 self.left.preorder_print()
 if self.right:
 self.right.preorder_print()
 return
 
 def postorder_print(self):
 if self.left:
 self.left.postorder_print()
 if self.right:
 self.right.postorder_print()
 print(self.val)
 return
 def inorder_print(self):
 if self.left:
 self.left.inorder_print()
 print(self.val)
 if self.right:
 self.right.inorder_print()
 return
 def bread_traversal_print(self):
 q=Queue()
 q.push(self)
 def bt():
 #import pdb;pdb.set_trace
 if not q:
 return
 node=q.pop()
 if node:
 if node.left:
 q.push(node.left)
 if node.right:
 q.push(node.right)
 print(node.val)
 bt()
 bt()
 
class Queue():
 def __init__(self):
 self.data = []
 def push(self,elt):
 self.data.append(elt)
 
 def pop(self):
 if self.data:
 return self.data.pop(0)
 def peek(self):
 if self.data:
 return self.data[0]
if __name__ == "__main__":
 #input = [l for l in 'FDJBEGKACIH']
 root = Node(1)
 root.left = Node(2)
 root.right = Node(3)
 root.left.left = Node(4)
 root.left.right = Node(5)
 root.right.left = Node(6)
 root.right.right = Node(7)
 print("preorder:")
 root.preorder_print()
 print("postorder:")
 root.postorder_print()
 print("inorder:")
 root.inorder_print()
 print('bread :')
 root.bread_traversal_print()
 """ 1
 2 3
 4 5 6 7
 [1 2 4 5 3 6 7]
 """

EDIT: Yes BFS for Breadth First Search would be more appropriate ;)

• superb rain: Ok so bread is first, but what's for dessert? :-P

Answer 1

Class definition

There is no need to explicitly inherit from object; that is a Python 2.x anachronism.

Instead of class Node(object):, simply write class Node:.

Similarly, class Queue(): can simply be class Queue:.

Default Parameters

Every Node should have a value; there is little reason to provide a default of 0 for the val parameter. By forcing the caller to provide the value, you are less likely to accidentally have a node with the default integer 0 value when all the other nodes are created with (say) strings.

Unnecessary returns

There is no need for the return statements in preorder_print, postorder_print, and inorder_print.

Visitor pattern

You have defined several methods for traversing the tree. All of them print the values. If you wanted to do anything else with the values, you're stuck writing another (set of 4?) function.

Instead, you should separate the traversal from the operation. Visit each node, in some order, and do something at that node.

class Node:
 ...
 def preorder(self, visitor):
 visitor(self.val)
 if self.left:
 self.left.preorder(visitor)
 if self.right:
 self.preorder(visitor)
 ...
# Do a pre-order traversal the tree, starting at the root, printing each values.
root.preorder(print)

Breadth First Traversal

First, the function should probably be called breadth_traversal_print, not bread_traversal_print.

Second, there is no need to use recursion during a breadth first traversal. You have a Queue which keeps track of the nodes you need to visit. You just need to loop while the queue is not empty. The recursion is doing a loop in a resource-intensive fashion. If Python had tail-call-optimization, the inefficiency could be removed automatically; but Python doesn't, so looping this way is wrong.

 def breadth_traversal_print(self):
 q = Queue()
 q.push(self)
 while q:
 node = q.pop()
 if node:
 if node.left:
 q.push(node.left)
 if node.right:
 q.push(node.right)
 print(node.val)

PEP-8

The PEP 8 -- Style Guide for Python enumerates many style guidelines all programs should follow.

White Space

There should be a space around binary operators, like =. You violate this with q=Queue(). Note that = used with keyword arguments is not an operator, so doesn't shouldn't be surrounded by white space; therefore def __init__(self, val=0, left=None, right=None): is correct.

There should be a space after commas. You violate this in def push(self,elt):

No-op code

This string ...

 """ 1
 2 3
 4 5 6 7
 [1 2 4 5 3 6 7]
 """

... is a statement which does nothing, and has no side-effect. Perhaps you meant this to be a comment?

NOTE: This is different from """docstrings""". A string statement which immediately follows a class or def statement is treated as a docstring, removed from the program code, and stored in the __doc__ member of the class or function by the Python interpreter. There, it can be extracted by help(...) and other documentation generation programs.

• curious: For the last comment, it is effectively not a string but a coment to help vizualize the test case in the if name =main part! IS it bad practice to include such string to help the reader to understand the test case ?
• AJNeufeld: If it is a comment, then syntactically is should be written as a comment, not as a string. As far as helping visualize the test case, it is beneath the breadth first traversal test case, but shows a list of the pre-order's output from several tests earlier. Running four "test cases", but showing the output for only one of them, and not bothering to specify which one it is, is not exactly helping the reader.