# DFS in a binary tree

Problem statement: Perform a depth first traversal on a BST and print the elements traversed.

class Node(object):
def __init__(self, value, left=None, right=None):
self.value = value
self.left = left
self.right = right

class BST(object):
def __init__(self, value):
self.root = Node(value)

def insert(self, value):
current = self.root
while current:
if value > current.value:
if current.right is None:
current.right  = Node(value)
break
else:
current = current.right
else:
if current.left is None :
current.left  = Node(value)
break
else:
current = current.left

def preorder(self,root):
## root,left,right

if root:
print root.value
if root.left:
self.preorder(root.left)
if root.right:
self.preorder(root.right)

def postorder(self,root):
## left, right, root

if root:
if root.left:
self.postorder(root.left)
if root.right:
self.postorder(root.right)
print root.value

def inorder(self,root):
## left, root, right

if root.left:
self.inorder(root.left)
print root.value
if root.right:
self.inorder(root.right)

t = BST(100)
t.insert(12)
t.insert(92)
t.insert(112)
t.insert(123)
t.insert(2)
t.insert(11)
t.insert(52)
t.insert(3)
t.insert(66)
t.insert(10)
print "preorder traversal is this "
t.preorder(t.root)
print "postorder traversal is this "
t.postorder(t.root)
print "inorder traversal is this "
t.inorder(t.root)


How can this code be more efficient?

This code is pretty much the most efficient it can be, so I will add some pointers on the coding style and convention.

1. Instead of calling your Binary Search Tree class a BST, define it as

class BinarySearchTree(object):


Gives more meaning to the class name.

2. The preorder traversal is called like t.preorder(t.root). But wait, t already has the root node in it, so it would be much more readable if we could do t.preorder(). So modify the signature to:

def preorder(self, root=None):
if root is None:
root = self.root


Same should be done for t.inorder() and t.postorder() as well.

1. Spaces: You need a space between your arguments, as recommended by PEP-0008. So do def inorder(self, root): instead of def inorder(self,root):. This goes for the inorder and postorder as well

2. Using root as the argument name is misleading - its better to call it as node, which has the default value of self.root. This is cleaner, since in the DFS, you would traverse all the nodes of the tree.

def preorder(self, node=None):
# replace root with node in your code


Same should be done for inorder and postorder as well.

    def inorder(self,root):
## left, root, right


Try defing them in the form of docstrings

def inorder(self,root):
"""traversal order: left child node, current node, right child node"""

• Good review! In points 2 and 4, def preorder(self, node=self.root): won't work as you intend because default values are evaluated at method definition time, not at call time. You need something like def preorder(self, node=None): and then if node is None: node=self.root. – Gareth Rees Apr 13 '18 at 9:01
• @GarethRees Yes, you are right, I've edited the section. I just realised though that in this case, the id node=None check evaluates every time, and am investigating ways to do it better. – mu 無 Apr 14 '18 at 8:36
• You should actually stick to what @GarethRees recommended and use if root is None: instead of if root == None:. See for example here for a reason why. – Graipher Apr 20 '18 at 9:30

this code looks quite good already, especially if you integrate the tips of the other answer

# return value

One problem I see though is that if you want to use your tree for something else than printing, it's not possible. This can be easily fixed by making the searches into iterators, and then print the elements

def inorder(self, node=None):
"""traversal order: left child node, current node, right child node"""
if node is None:
node = self.root
if node.left:
for node in self.inorder(node.left)
yield node
yield node.value
if node.right:
for node in self.inorder(node .right)
yield node

for node in t.inorder(t.root)
print(node)


# Getting a node

I see no way to get a node?

Perhaps a method to add multiple nodes at the same time would ease initialization

# alternative approach

Another approach could be to let the traversal be a method of Node instead of the tree. You can even make a generic Node.traversal method

def traverse(self, order=('left', 'self', 'right'):
orders = {
'inorder': ('left', 'self', 'right',),
'preorder': ('self', 'left', 'right',),
'postorder': ('left', 'right', 'self',),
'reverse': ('right', 'self', 'left',),
}

try:
order = orders[order]
except KeyError, TypeError:
errormsg = ''''order should be one of {} or only contain ('left', 'self', 'right')'''.format(set(orders.keys()))
assert set(order) <={'left', 'self', 'right'}, errormsg

for element in order:
if element == 'left' and self.left is not None:
yield from self.left.traverse(order=order)
if element == 'self'
yield  self.value
if element == 'right' and self.right is not None:
yield from self.right.traverse(order=order)


This code will probably be slightly slower than a dedicated method for each mode of traversal, but it is more versatile and contains less repetition, so easier from a maintenance point