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)

Zbynek Vyskovsky - kvr000 · Accepted Answer · 2016-02-13 21:07:13Z

3

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())

answered Feb 13, 2016 at 21:07

Zbynek Vyskovsky - kvr000

19.1k3 gold badges41 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

deets · Accepted Answer · 2016-02-13 21:11:07Z

1

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()
        ...

answered Feb 13, 2016 at 21:11

deets

6,40531 silver badges29 bronze badges

3 Comments

tulians Over a year ago

You mean that I should access anywhere in the code the children nodes as node.right_child and node.left_child?

deets Over a year ago

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 Over a year ago

Looks much better without the one-liners accessors. Thanks for making me note that!

Forge · Accepted Answer · 2016-02-13 21:11:43Z

0

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

answered Feb 13, 2016 at 21:11

Forge

6,8727 gold badges49 silver badges65 bronze badges

Collectives™ on Stack Overflow

Error while traversing binary search tree - Python

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related