Error while traversing binary search tree - Python

Question

I'm trying to run the classic algorithms for tree traversing. I've created an example tree and tested whether the preorder, inorder and postorder algorithms worked correctly. But after that tests I get incorrect results. When I run the preorder algorithm starting on node A, I get this sequence {A,C,H,D,G}, when I should be getting {A,C,D,H,G}.

I don't think I'm missing something in the traversing part of the code, but maybe I am in the tree definition. I can't see the error myself.

class Node:
 id = 0
 def __init__(self,value):
 self.id = id
 Node.id += 1
 self.value = value
 self.left_child = None
 self.right_child = None
 def insert_left_child(self, new_node):
 if self.is_leaf():
 self.insert_left_child(new_node);
 else:
 # As there is already a left child, the pointers must be
 # redistributed to include the new child. 
 current_left_child = self.left_subtree()
 self.insert_left_child(new_node)
 new_node.insert_left_child(current_left_child)
 def insert_right_child(self, new_node):
 if self.is_leaf():
 self.insert_right_child(new_node);
 else:
 # As there is already a right child, the pointers must be
 # redistributed to include the new child.
 current_right_child = self.right_subtree()
 self.insert_right_child(new_node)
 new_node.insert_right_child(current_right_child)
 def left_subtree(self):
 return self.left_child
 def right_subtree(self):
 return self.right_child
 def insert_left_child(self,child_node):
 self.left_child = child_node
 def has_left_children(self):
 return self.left_child != None
 def insert_right_child(self,child_node):
 self.right_child = child_node
 def has_right_children(self):
 return self.right_child != None
 def is_leaf(self):
 return (not self.has_left_children()) & (not self.has_right_children())
class BinaryTree:
 def __init__(self):
 self.root = Node('root')
 def preorder(self,current_node = None):
 if current_node is None:
 current_node = self.root
 print current_node.value
 if current_node.has_left_children():
 self.inorder(current_node.left_subtree())
 if current_node.has_right_children():
 self.inorder(current_node.right_subtree())
 def inorder(self,current_node = None):
 if current_node is None:
 current_node = self.root
 if current_node.has_left_children():
 self.inorder(current_node.left_subtree())
 print current_node.value
 if current_node.has_right_children():
 self.inorder(current_node.right_subtree())
 def postorder(self,current_node = None):
 if current_node is None:
 current_node = self.root
 if current_node.has_left_children():
 self.inorder(current_node.left_subtree())
 if current_node.has_right_children():
 self.inorder(current_node.right_subtree())
 print current_node.value
# Main routine
# root
# A B
# C D E F
# H G
tree = BinaryTree()
A = Node('A')
B = Node('B')
C = Node('C')
D = Node('D')
E = Node('E')
F = Node('F')
G = Node('G')
H = Node('H')
tree.root.insert_left_child(A)
tree.root.insert_right_child(B)
A.insert_left_child(C)
A.insert_right_child(D)
B.insert_left_child(E)
B.insert_right_child(F)
D.insert_left_child(H)
D.insert_right_child(G)
tree.preorder(A)

Answer 1

You call inorder methods from preorder method. So you change the algorithm when getting deeper in the tree:

 if current_node.has_left_children():
 self.inorder(current_node.left_subtree())
 if current_node.has_right_children():
 self.inorder(current_node.right_subtree())

should be:

 if current_node.has_left_children():
 self.preorder(current_node.left_subtree())
 if current_node.has_right_children():
 self.preorder(current_node.right_subtree())

Answer 2

There is a lot to be said about this code. You should get rid of all the superfluous accessor-methods, and access left and right children immediately. Also, consider making e.g. is_leaf a property instead of a method. But the thing that probably causes your error is the following:

class Node:
 id = 0
 def __init__(self,value):
 self.id = id
 Node.id += 1

This does not do what you think it does. It assigns the builtin function "id" to your id, thus making all nodes the same id.

To fix this, either use Node.id, or even better, use this:

from itertools import count
class Node(object): # if on python3, you don't need to inherit from object
 IDGEN = count()
 def __init__(self, value):
 self.id = self.IDGEN.next()
 ...

• tulians: You mean that I should access anywhere in the code the children nodes as node.right_child and node.left_child?
• deets: Exactly. There is a famous quib "Python is not Java". You do not build accessor-methods. If you need to change the semantics of accessing an attribute, make it a property instead. Removing all this unnecessary accessor methods will remove 50% of your code - and less code is better!
• tulians: Looks much better without the one-liners accessors. Thanks for making me note that!

Answer 3

Copy-Paste error here, you are mistakenly calling inorder in preorder (and postorder).