current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite
1
 
class BinaryTree(object):

    def __init__(self, rootObj):
        self.key = rootObj
        self.leftChild = None
        self.rightChild = None

    def insertLeftChild(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            newBinaryTree = BinaryTree(newNode)
            newBinaryTree.leftChild = self.leftChild
            self.leftChild = newBinaryTree
        return self.leftChild

    def insertRightChild(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            newBinaryTree = BinaryTree(newNode)
            newBinaryTree.rightChild = newNode
            self.rightChild = newBinaryTree
        return self.rightChild

    def getRoot(self):
        return self.key

    def setRoot(self, obj):
        self.key = obj

    def getLeftChild(self):
        return self.leftChild

    def getRightChild(self):
        return self.rightChild

    def __str__(self):
        return '%s' % self.key

    # DFS traversal techniques.
    @classmethod
    def preorder(cls, node):
        if node == None: return False
        print node
        cls.preorder(node.getLeftChild())
        cls.preorder(node.getRightChild())

    @classmethod
    def inorder(cls, node):
        if node == None: return False
        cls.inorder(node.getLeftChild())
        print node
        cls.inorder(node.getRightChild())

    @classmethod
    def postorder(cls, node):
        if node == None: return False
        cls.inorder(node.getLeftChild())
        cls.inorder(node.getRightChild())
        print node


def buildTree():
    root = BinaryTree('a')
    firstLeft = root.insertLeftChild('b')
    firstRight = root.insertRightChild('c')
    firstLeft.insertRightChild('d')
    firstRight.insertLeftChild('e')
    firstRight.insertRightChild('f')
    return root

if __name__ == '__main__':
    binaryTree = buildTree()
    print 'Preorder'
    print BinaryTree.preorder(binaryTree)
    print 'Inorder'
    print BinaryTree.inorder(binaryTree)
    print 'Postorder'
    print BinaryTree.postorder(binaryTree)
share|improve this question
    
Also, can anyone suggest me how to unittest this code? or guide me to some proper documentation? –  vivekpoddar Oct 30 '14 at 10:27
1  
Do you mean how to unit test in general, or how to use unittest specifically? Either way, there is plenty of documentation out there already. –  jonrsharpe Oct 30 '14 at 11:01
2  
You should post the question in the post, and not as a comment –  usethedeathstar Oct 30 '14 at 12:42
    
What you may and may not do after receiving answers. I've rolled back Rev 4 → 3. –  200_success♦ Nov 7 '14 at 3:53

4 Answers 4

up vote 5 down vote accepted
+50

As evidenced by the bug in Rev 1, the inconsistent naming between getRoot()/setRoot() and self.key is a trap that you've created for yourself.

Getters and setters would be better done using the @property decorator. Follow the convention in the documentation:

class BinaryTree(object):
    def __init__(self, obj):
        self.obj = obj
        self.left_child = self.right_child = None

    @property
    def obj(self):
        """The datum stored in the node."""
        return self._obj

    @obj.setter
    def obj(self, value):
        self._obj = value

    def __str__(self):
        return str(self.obj)    # <-- Simpler than %s interpolation

    …

Your traversal algorithms should not have a print statement, as they would be useless for anything other than printing to sys.stdout. Instead, they should yield each result. The caller can then choose to print them or do whatever it pleases.

for obj in pre_order(root):
    print obj

A nice way to write simple unit tests and provide documentation at the same time is to use the doctest module.

share|improve this answer
    
I tried yield in place of the print but I am getting only first element, maybe my function is recursive which is returning another generator. Updated the above post to include the new method definition. –  vivekpoddar Oct 31 '14 at 10:47
    
How to use yield in a recursive function? –  vivekpoddar Nov 7 '14 at 4:04
    
Exactly like I wrote. Change print to yield, then iterate using a for loop. –  200_success♦ Nov 7 '14 at 4:30
up vote 4 down vote

A few comments:

  • There is no explanation anywhere of what is supposed to be happening. Consider adding docstrings to your methods; I like the Google style, but others are available.

  • Your code isn't compliant with the style guide; methods, attributes and instances should be named using lower_case_with_underscores not mixedCase.

  • It's not clear why inorder, preorder and postorder are class, rather than instance, methods (this could be explained in docstrings!) binaryTree.inorder() seems much neater than BinaryTree.postorder(binaryTree).

  • buildTree, on the other hand, probably should be a class method, rather than a standalone function (binaryTree = BinaryTree.buildTree()).

share|improve this answer
    
Sure, I will try to follow the style guide and update the code also, buildTree is just a test function. –  vivekpoddar Oct 30 '14 at 10:21
    
Regarding inorder, preorder I had some confusion but I thought in terms of functional programming. –  vivekpoddar Oct 30 '14 at 10:24
    
What do you mean "in terms of functional programming"? –  jonrsharpe Oct 30 '14 at 10:52
    
Simply, I didn't wanted to tie that method to a particular instance i.e. given a obj of BinaryTree type it could traverse it. –  vivekpoddar Oct 30 '14 at 10:53
up vote 3 down vote

There is a issue with how you are handling the payload for the tree. The property for it is called "Key" which is okay, but the constructor argument is calling it an object. So are we storing a value or a data structure? If it is a data structure, then payload would probably be a better name.

I also see problems with the Insert methods. The argument named newNode is misleading (along with rootObj in the constructor). I'm assuming an instance of BinaryTreeNode (which isn't present) or BinaryTree to be passed in here because of the name of the argument. Also in these methods the abstraction barrier is broken by directly manipulating the new binary tree property (newBinaryTree.rightChild = newNode) instead of calling its own insert method but not a huge problem. If you made the left and right child private/protected members, this could break your code (based on language used).

The getRoot and setRoot methods are wrong as well. getRoot should be a recursive function that navigates from a given node up the tree to the top most node. Instead it is accessing the payload of the node. Set root isn't taking the tree twig and breaking it off from the parent tree. Instead they are acting as getters and setters for the payload of the node.

If you want the getRoot and setRoot methods to do what the names suggests, you need to add a reference back to the parent tree when inserting nodes.

share|improve this answer
up vote 0 down vote

Don't repeat yourself

Let's refactor this original code step by step, simply by removing unnecessary repetitions and see where it gets us:

if self.leftChild == None:
    self.leftChild = BinaryTree(newNode)
else:
    newBinaryTree = BinaryTree(newNode)
    newBinaryTree.leftChild = self.leftChild
    self.leftChild = newBinaryTree
return self.leftChild

Notice that BinaryTree(newNode) appears in both branches of the if-else. It's better to create it before the if-else:

newBinaryTree = BinaryTree(newNode)
if self.leftChild == None:
    self.leftChild = newBinaryTree
else:
    newBinaryTree.leftChild = self.leftChild
    self.leftChild = newBinaryTree
return self.leftChild

Notice that self.leftChild = newBinaryTree appears in both branches of the if-else. It's better to do that after the if-else:

newBinaryTree = BinaryTree(newNode)
if self.leftChild is not None:
    newBinaryTree.leftChild = self.leftChild
self.leftChild = newBinaryTree
return self.leftChild

Follow the same logic in insertRightChild too.

Strange naming

In insertRightChild and insertLeftChild, the parameter name newNode is outright disturbing: a "node" is usually a complex object wrapping some data contained within and linking to other objects, in a tree or linked list. Here, it's really just data. So it should be named accordingly.

Simplify the names

I think in a BinaryTree class it's perfectly natural to assume that there will be left and right child elements. So I would drop the word "child" everywhere. Redundant text is annoying and hurts readability. left and right are short and sweet and perfectly clear.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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