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

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.