Reputation: 111
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
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