6
\$\begingroup\$

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?

\$\endgroup\$
8
\$\begingroup\$

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.

  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.

  3. 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
    
| improve this answer | |
\$\endgroup\$
  • 4
    \$\begingroup\$ 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. \$\endgroup\$ – Gareth Rees Apr 13 '18 at 9:01
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – mu 無 Apr 14 '18 at 8:36
  • \$\begingroup\$ 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. \$\endgroup\$ – Graipher Apr 20 '18 at 9:30
5
\$\begingroup\$

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

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.