Tree structure with support for inorder and preorder traversal

Question

I am learning Tree Data Structures and came up with this code for implementing basic Tree Node using class and performing various Tree based operations like Traversals and others. The code works perfectly but the structure is bothering me a lot, such as this line of code here:

print(tree.size(tree))

How can I improve the code structure?

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

    def __str__(self):
        return self.data

    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(node.data)
            self.inorder(node.right)

    def preorder(self, node):
        if node is not None:
            print(node.data)
            self.preorder(node.left)
            self.preorder(node.right)

    def size(self, node):
        if node is None:
            return 0
        return self.size(node.left) + 1 + self.size(node.right)


tree = Node(1)
tree.left = Node(2)
tree.right = Node(3)
tree.left.left = Node(4)
tree.left.right = Node(5)

print(tree.size(tree))

Answer 1

Your instinct to question the appropriateness of tree.size(tree) is right. You should be able to write tree.size() instead. The problem is that you've written the methods to take a node parameter, when in fact self is a Node.

Therefore, you should define

def size(self):
    return 1 + (self.left.size()  if self.left  is not None else 0) \
             + (self.right.size() if self.right is not None else 0)

so that you can write tree.size().

---

The __str__ method isn't right: there's nothing that says that data is a string. (In fact, in your example, they are integers.) A more reasonable implementation would be

def __str__(self):
    return str(self.data)

---

It would be better to avoid hard-coding the print() calls in inorder and preorder, so that they can be used to do more than just printing. In Python, it would be better to yield each datum, so that inorder() and preorder() act as generators. (Note that this uses yield from, introduced in Python 3.3.)

def inorder(self):
    if self.left is not None:
        yield from self.left.inorder()
    yield self.data
    if self.right is not None:
        yield from self.right.inorder()

… to be called like

for data in tree.inorder():
    print(data)

You would then have the flexibility to write something like sum(data for data in tree.inorder()) to add all of the nodes.

Answer 2

Caveat: I'm taking the code seriously

Background

The abstractions are leaky.

What is a Node?

A node has two parts: the value it contains and pointers to other nodes. Either, both, or neither may be null. When the pointer part is null we have a terminal node. Depending on context a terminal node might be called a leaf or an atom.

Graphs

One or more nodes form a graph. A graph may be directed or non-directed. Some, all, or none of the nodes in a graph may point to other nodes within it. The way in which nodes point to each other is what distinguishes one type of graph from another. Whether a node contains null or some other value is a detail of a graph implementation not nodes. A node's pointers to other nodes are the edges of a graph. The value stored at the node is a record.

The structure of a record is not a function of the graph or the node. It is an implementation detail of a particular program. That is to say that the record structure reflects business logic.

The edges of a directed graph are directional. The directed edge a -> b is different from the directed edge b -> a. The edges of a non-directed graph are not directional. The non-directed edge a - b is indistinguishable from the non-directed edge b - a.

Traversal is an operation on graphs. The order is not a property of the graph. It is a property of the business logic. The efficiency with which we traverse a graph often depends on the alignment between business logic and graph type.

Trees

Trees are a class of directed acyclic graphs. A graph consisting of a single node is a tree provided that it does not have an edge pointing to itself. A graph that consists of several trees is called a forest.

A tree in which each node n has two outgoing edges is a binary tree. Typically, one edge is labeled left, the other right. A binary tree may or may not store values at internal nodes depending on the business logic being implemented. Binary trees are of particular interest in computing due to their isomorphism with binary logic. Another important class of trees for computing is the b-tree.

Code Improvements

To a first approximation, the leaky abstractions can be removed by redefining Node and then using it in a definition of a BinaryTree.

A Node Implementation

Since the number of edges a node has is a function of both the graph type and a particular instantiation of that type, an iterable data structure makes sense. A list is probably the place to start.

class Node():
    def __init__(self, record):
        self.edge = []
        self.record = record

A Binary Tree Implementation

Now, binary trees can be implemented in terms of nodes.

class BinaryTree():
    def __init__(self, record):
        node = Node(record)
        node.edge = [False, False]
        self.record = node.record
        self.left = node.edge[0]
        self.right = node.edge[1]

Note that the Node is encapsulated. There are accessors for the left and right edges, but no way to delete or add elements to node.edge. Its length will always be two, there's no way to add a third edge to a BinaryTree.

However, More Work Remains

The abstraction is still poor because Node contains knowledge of edges. The right abstraction is a graph. A graph consists of nodes, usually called vertices, and edges.

• All a vertex should know is how to return a value. Anything it knows about edges is the graph abstraction leaking downward.
• Likewise all an edge should know is the name of two vertices. If it knows anything about direction, the graph abstraction is leaking down. If it knows anything about the contents behind the labels, the vertex abstraction is leaking up.

Graph Implementation

class Vertex():
  def __init__(self, value):
    self.value = value

class Graph():
  def __init__(self, V, E):
    self.V = [] 
    self.E = {}

Using a dictionary for edges allows finding the edges that start at a node. Vertices are implicitly labelled by position in the list. A fast lookup array would be better but requires declaring datatypes.

Answer 3

What is an empty tree?

Well, it looks like it should be None, but None isn't a tree. This implies you've probably got the abstraction layer in the wrong place. The other hint is that most of your methods take node as an input instead of using self; 200_success shows you one way of fixing it but it involves changing the code from the ideal.

What you'd really like is a structure that encapsulates this.

class Tree:
    def __init__(self, root=None):
        self.root = root

    def __str__(self):
        return ???

    def inorder(self):
        return inorder(self.root)

    def preorder(self):
        return preorder(self.root)

    def size(self):
        return sizeof(self.root)

Then dispell with the idea that everything has to be a member function; inorder, preorder and size are all algorithms on a node and its children, but that Node can be None and this is impossible to express by looking at self (alternatively you could use an option type, but this isn't neatly expressed in Python).

def inorder(node):
    if node is not None:
        inorder(node.left)
        print(node.data)
        inorder(node.right)

def preorder(node):
    if node is not None:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

def sizeof(node):
    if node is None:
        return 0
    return size(node.left) + 1 + size(node.right)

Now, best if one instead yields values rather than print them:

def inorder(node):
    if node is not None:
        yield from inorder(node.left)
        yield node.data
        yield from inorder(node.right)

def preorder(node):
    if node is not None:
        yield node.data
        yield from preorder(node.left)
        yield from preorder(node.right)

Now, you might wonder why bother having Tree at all; Node with non-member functions seems to do fine. This is true; the only advantage of Tree currently is that it collects member functions into a well-defined scope. However, this is not always worthwhile, and you should feel free to just stick with using non-member functions.

I would reconsider __str__. A direct translation would be

return self.root.data

but this fails to always give a string. This also fails:

return str(self.root.data)

when self.root is None. It also gives the appearance that a tree is its first elements. I would do:

return "Tree({})".format(self.root)

and change Node to

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

    def __str__(self):
        if self.right is None:
            if self.left is None:
                return "Node({})".format(self.data)
            return "Node({}, {})".format(self.data, self.left)
        return "Node({}, {}, {})".format(self.data, self.left, self.right)

which gives something like Tree(Node(1, Node(2, Node(4), Node(5)), Node(3))). This happens to then be a legal invocation of Tree, so change it to __repr__.

But now note that an empty tree is Tree(None), has a size of 0 and an empty but legal iterable is produced from inorder and preorder.