DFS in a binary tree

Question

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?

Answer 1

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):
       # remainder of your code
   

   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
       # remainder of your code
   

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

3. 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

4. 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.

5. Comments and indentation: Your comments are currently not indented right. Instead of having

       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"""
       # remainder of your code
   

Answer 2

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?

Add multiple nodes

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