Ganesh Thampi
Ganesh Thampi

Reputation: 111

Recursive Pre-order Binary Tree Traversal in Python - Nonetype Error

I am having issues with a helper method in my code. I providing both correct and incorrect approaches to the problem but I fail to see the difference between the two.

My approach :

def preorder_print(self, start, traversal):
        if start == None:
            return traversal
        else:
            traversal += str(start.value)
            traversal = self.preorder_print(start.left,traversal)
            traversal = self.preorder_print(start.right,traversal)

Note : start is the root node and traversal is an empty string

This gives TypeError: unsupported operand type(s) for +=: 'NoneType' and 'str'

The correct approach :

def preorder_print(self, start, traversal):
        if start:
            traversal += str(start.value) 
            traversal = self.preorder_print(start.left, traversal)
            traversal = self.preorder_print(start.right, traversal)
        return traversal

I am unable to understand the difference between these two approaches. Can someone explain how the two approaches differ in execution.

Upvotes: 0

Views: 492

Answers (1)

Mulan
Mulan

Reputation: 135227

In this answer, we separate preorder traversal logic from the the computation/effect. Starting with a node class -

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

And here's the tree class -

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

  @property
  def is_empty(self):
    return self.root is None

  @property
  def data(self):
    return self.root.data

  @property
  def left(self):
    return self.root.left

  @property
  def right(self):
    return self.root.right

  def preorder(self):
    if not self.is_empty:
      yield self.data
      yield from tree(self.left).preorder()
      yield from tree(self.right).preorder()

Let's create a root node -

root = node \
  ( 1
  , node(2, node(3), node(4))
  , node(5, node(6), node(7))
  )

Which represents this tree -

      1
     / \
    /   \
   2     5
  / \   / \
 3   4 6   7

Now we can print the whole tree -

for val in tree(root).preorder():
  print(val)

# 1
# 2
# 3
# 4
# 5
# 6
# 7

It's important to keep traversal of our tree separate from the computations we make on the tree's values. For example, we can easily sum the values -

print(sum(tree(root).preorder()))
# 28

Or we can collect all of the values in an ordered list -

print(list(tree(root).preorder()))
# [1, 2, 3, 4, 5, 6, 7]

If print is a part of preorder, you'll have to duplicate the preorder traversal logic for every other tree operation you wish to implement.


best practice

You should probably safeguard against accessing properties on an empty node -

class tree:

  # ...

  @property
  def data(self):
    if self.is_empty:
      raise Exception("cannot get data of an empty tree")
    else:
      return self.root.data

  @property
  def left(self):
    if self.is_empty:
      raise Exception("cannot get left of an empty tree")
    else:
      return self.root.left

  @property
  def right(self):
    if self.is_empty:
      raise Exception("cannot get right of an empty tree")
    else:
      return self.root.right

other traversals

Now imagine you want to traverse your tree in other ways, such as inorder or postorder. Mixing computations/effects like print or + means you will have even more duplication. We'll definitely want to avoid that -

class tree:
  # ...
  def inorder(self):
    if not self.is_empty:
      yield from tree(self.left).inorder()
      yield self.data
      yield from tree(self.right).inorder()

  def postorder(self):
    if not self.is_empty:
      yield from tree(self.left).postorder()
      yield from tree(self.right).postorder()
      yield self.data

For reference, here's our tree again -

      1
     / \
    /   \
   2     5
  / \   / \
 3   4 6   7

Here's inorder traversal at work -

print(list(tree(root).inorder()))
# [3, 2, 4, 1, 6, 5, 7]

print(sum(tree(root).inorder()))
# 28

And postorder -

print(list(tree(root).postorder()))
# [3, 4, 2, 6, 7, 5, 1]

print(sum(tree(root).postorder()))
# 28

Upvotes: 1

Related Questions