Binary tree in Python exercise

Question

I'm practicing Python. Being completely new to the language I'd like to hear someone else thoughts on the way I use the language. I'm coming from (mainly) Java and C so I'd expect new ways of doing stuff offered by Python which I am surely not aware of because I'm still learning.

I came up with a very simple implementation for a binary tree. The idea is to practice with classes in Python. The tree supports just inserting elements and traversing pre-order, in-order and post-order. I'm not concerned about the functionality but more about comments.

from __future__ import print_function
import math
import os

class BinaryTree:
    __left = None
    __right = None
    __value = None

    def __init__(self):
        return

    def addValue(self, value):
        if self.__value is None:
            self.__value = value

        elif value > self.__value:
            if self.__right is None:
                self.__right = BinaryTree()
            self.__right.addValue(value)

        elif value < self.__value:
            if self.__left is None:
                self.__left = BinaryTree()
            self.__left.addValue(value)

        return

    def preOrderTraverse(self):
        """
        Performs a pre-order traversal of the tree.
        Returns the list of elements
        """
        elements = []
        if self.__value is not None:
            # Visit the root node first
            elements.append(self.__value)
            # Then visit the left node if present
            if self.__left is not None:
                elements += self.__left.preOrderTraverse()
            # Then visit the right node if present
            if self.__right is not None:
                elements += self.__right.preOrderTraverse()

        return elements

    def inOrderTraverse(self):
        """
        Performs a in-order traversal of the tree.
        Returns the list of elements
        """
        elements = []
        if self.__value is not None:
            # Visit the left node first if present
            if self.__left is not None:
                elements += self.__left.inOrderTraverse()
            # Then visit the root node
            elements.append(self.__value)
            # Then visit the right node if present
            if self.__right is not None:
                elements += self.__right.inOrderTraverse()

        return elements


    def postOrderTraverse(self):
        """
        Performs a post-order traversal of the tree.
        Returns the list of elements
        """
        elements = []
        if self.__value is not None:
            # Visit the left node first if present
            if self.__left is not None:
                elements += self.__left.postOrderTraverse()
            # Then visit the right node if present
            if self.__right is not None:
                elements += self.__right.postOrderTraverse()
            # Then visit the root node
            elements.append(self.__value)

        return elements


if __name__ == "__main__":
    binarytree = BinaryTree()
    binarytree.addValue(23)
    binarytree.addValue(15)
    binarytree.addValue(19)
    binarytree.addValue(8)
    binarytree.addValue(7)
    binarytree.addValue(42)
    binarytree.addValue(0)
    binarytree.addValue(1)
    elements = binarytree.preOrderTraverse()

    print("Pre order traversal: ", end="")
    for val in elements:
        print(val, end=" ")

    print("")

    elements = binarytree.inOrderTraverse()

    print("In order traversal: ", end="")
    for val in elements:
        print(val, end=" ")

    print("")

    elements = binarytree.postOrderTraverse()

    print("Post order traversal: ", end="")
    for val in elements:
        print(val, end=" ")

    print("")

Answer 1

PEP 8 says

You have minor issues with the code layout:

1. PEP 8 requires two empty lines before the class definition,
2. Modules os and math are not used,
3. In addValue the return statement is unnecessary,
4. PEP 8 proposes the method names in this_format; rename addValue to add_value.

Improving the code

I suggest you try to take use of a visitor pattern: in your traversal methods add new argument taking a function that is called with a current binary tree node. I had this in mind:

from __future__ import print_function


class BinaryTree:
    def __init__(self):
        self.__left = None
        self.__right = None
        self.__value = None

    def add_value(self, value):
        if self.__value is None:
            self.__value = value

        elif value > self.__value:
            if self.__right is None:
                self.__right = BinaryTree()
            self.__right.add_value(value)

        elif value < self.__value:
            if self.__left is None:
                self.__left = BinaryTree()
            self.__left.add_value(value)

    def pre_order_traverse(self, visitor_func=None):
        """
        Performs a pre-order traversal of the tree.
        Returns the list of elements
        """
        if self.__value is not None:
            # Visit the root node first
            if visitor_func:
                visitor_func(self.__value)
            # Then visit the left node if present
            if self.__left is not None:
                self.__left.pre_order_traverse(visitor_func)
            # Then visit the right node if present
            if self.__right is not None:
                self.__right.pre_order_traverse(visitor_func)

    def in_order_traverse(self, visitor_func=None):
        """
        Performs a in-order traversal of the tree.
        Returns the list of elements
        """
        if self.__value is not None:
            # Visit the left node first if present
            if self.__left is not None:
                self.__left.in_order_traverse(visitor_func)
            # Then visit the root node
            if visitor_func:
                visitor_func(self.__value)
            # Then visit the right node if present
            if self.__right is not None:
                self.__right.in_order_traverse(visitor_func)

    def post_order_traverse(self, visitor_func=None):
        """
        Performs a post-order traversal of the tree.
        Returns the list of elements
        """
        if self.__value is not None:
            # Visit the left node first if present
            if self.__left is not None:
                self.__left.post_order_traverse(visitor_func)
            # Then visit the right node if present
            if self.__right is not None:
                self.__right.post_order_traverse(visitor_func)
            # Then visit the root node
            if visitor_func:
                visitor_func(self.__value)


if __name__ == "__main__":
    binarytree = BinaryTree()
    binarytree.add_value(23)
    binarytree.add_value(15)
    binarytree.add_value(19)
    binarytree.add_value(8)
    binarytree.add_value(7)
    binarytree.add_value(42)
    binarytree.add_value(0)
    binarytree.add_value(1)

    def visitor1(value):
        print(value)

    class ElementVisitor:
        def __init__(self):
            self.elements = []

        def add(self, value):
            self.elements.append(value)

    ev = ElementVisitor()
    binarytree.pre_order_traverse(ev.add)
    print(ev.elements)

    print("")

    binarytree.in_order_traverse(visitor1)

    print("")

    binarytree.post_order_traverse(visitor1)

As you can see, above you can both print the nodes and collect them in a list; both by simply passing an appropriate function/object method.

Hope that helps.

Answer 2

@coderodde did a nice analysis I just want to extend a little bit. Side note about his review, you should definitely read the PEP8 specifications if you want to get into Python.

---

class BinaryTree:
    __left = None
    __right = None
    __value = None

    def __init__(self):
        return

You need to be careful with this one, since it is not handled the same way as defining variables into the __init__ function. Those are class variables. Technically, it does not change anything to your code (mostly because they are not mutable) but you should define instance dependent variables into the __init__ section. For more information, I highly suggest you to read documentation about Python's classes.

---

def __init__(self):
    return

Avoid using return when not needed. We expect a procedure not returning anything and using the return statement might be unexpected for the reader. Note that return may be used to stop the procedure in some cases, even if it might not be considered proper usage of return by some.

Also, some linters may ask you to provide some information about what you return if you use this statement somewhere in your code.

---

def pre_order_traverse(self, visitor_func=None):
    """
    Performs a pre-order traversal of the tree.
    Returns the list of elements
    """

From the PEP257:

Multi-line docstrings consist of a summary line just like a one-line docstring, followed by a blank line, followed by a more elaborate description. The summary line may be used by automatic indexing tools; it is important that it fits on one line and is separated from the rest of the docstring by a blank line. The summary line may be on the same line as the opening quotes or on the next line. The entire docstring is indented the same as the quotes at its first line (see example below).

Based on the Google Style Guide about docstrings, your comment should look like this (there are many other style guides for docstring, choose one and stick to it ;) ):

def pre_order_traverse(self, visitor_func=None):
    """Performs a pre-order traversal of the tree.

    Args:
        visitor_func: Function used on node values.
    """

Also, I note that most of the functions do nothing if no visitor_func are specified. You may want to pass this as non-default parameter, which will avoid one if statement.

---

if self.__value is not None:
    # Visit the left node first if present
    if self.__left is not None:
        self.__left.post_order_traverse(visitor_func)
    # ...

Those comments are overkilling the code. Extend the docstring to explain the implementation if needed.

def pre_order_traverse(self, visitor_func):
    """Performs a pre-order traversal of the tree.

    Print the root node first, visit the left part and then the right part.

    Args:
        visitor_func: Function used on node values.
    """
    if self.__value is not None:
        visitor_func(self.__value)
        if self.__left is not None:
            self.__left.pre_order_traverse(visitor_func)
        if self.__right is not None:
            self.__right.pre_order_traverse(visitor_func)

Answer 3

You've implemented a binary search tree, but without the search function that would make this data structure useful. But anyway… I'll review this code top-to-bottom.

---

Why import math and import os? Neither import is used.

Judging from from __future__ import print_function, this code is meant for Python 2.x. In Python 2, classes should explicitly inherit from object.

The double-underscores are inappropriate, and probably isn't what you intended. This…

class BinaryTree:
    __left = None
    __right = None
    __value = None

    def __init__(self):
        return

… is basically equivalent to…

class BinaryTree:
    def __init__(self):
        self._BinaryTree__left = None
        self._BinaryTree__right = None
        self._BinaryTree__value = None

The addValue method fails to take all possibilities into account. Sure, value might be less than or greater than self.__value, but it might also be None, or it could be equal to self.__value. If your data structure treats None as a special value, when you had better prohibit it from being used as valid data.

The traversal methods, rather than returning lists, would be better as iterators. In particular, it would be convenient to write them in Python as generators.

The demonstration code for constructing and printing a sample tree is a bit verbose.

Suggested solution

Note that I have renamed the methods using the lower_case_with_underscores convention specified by PEP 8.

from __future__ import print_function

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

    def add_value(self, value):
        """
        Add a value (which may not be None) to the tree.
        """
        if value is None:
            raise ValueError("Cannot add None as a value")
        elif self.value is None:
            self.value = value
        elif value > self.value:
            if self.right is None:
                self.right = BinaryTree()
            self.right.add_value(value)
        else:
            if self.left is None:
                self.left = BinaryTree()
            self.left.add_value(value)

    def pre_order_traverse(self):
        """
        Perform a pre-order traversal of the tree.
        """
        if self.value is not None:
            yield self.value
            if self.left is not None:
                for v in self.left.pre_order_traverse(): yield v
            if self.right is not None:
                for v in self.right.pre_order_traverse(): yield v

    def in_order_traverse(self):
        """
        Perform a in-order traversal of the tree.
        """
        if self.value is not None:
            if self.left is not None:
                for v in self.left.in_order_traverse(): yield v
            yield self.value
            if self.right is not None:
                for v in self.right.in_order_traverse(): yield v

    def post_order_traverse(self):
        """
        Perform a post-order traversal of the tree.
        """
        if self.value is not None:
            if self.left is not None:
                for v in self.left.post_order_traverse(): yield v
            if self.right is not None:
                for v in self.right.post_order_traverse(): yield v
            yield self.value


if __name__ == "__main__":
    binarytree = BinaryTree()
    for v in [23, 15, 19, 8, 7, 42, 0, 1]:
        binarytree.add_value(v)

    print("Pre order traversal: " +
          ' '.join(str(v) for v in binarytree.pre_order_traverse()))
    print("In order traversal: " +
          ' '.join(str(v) for v in binarytree.in_order_traverse()))
    print("Post order traversal: " +
          ' '.join(str(v) for v in binarytree.post_order_traverse()))

In Python ≥ 3.3, recursive generators could be even more simply written using yield from. Instead of

for v in self.left.pre_order_traverse(): yield v

… you could write:

yield from self.left.pre_order_traverse()