Inorder tree walk not working

Question

I am trying to practice BST tree implementation with python, following is my code,

import pdb

class Node():
    def __init__(self, parent=None, key=None):
        self.parent = parent if parent != None else None
        self.left = None
        self.right = None
        self.key = key if key != None else None

class BST():
    def __init__(self):
        self.root = Node() 

    def insertKey (self, key):
        #pdb.set_trace()
        # transverse till we find empty position
        if (self.root.key == None):
            self.root.key = key
        else:
            node = self.root
            while (node.left != None and node.right != None):
                if node.key < key:
                    node = node.right
                else:
                    node = node.left
            #we have node either left or right is empty
            if node.key < key:
                node.right = Node (node, key)
            else:
                node.left = Node (node, key)

    def inOrder (self, node):
        #pdb.set_trace()
        if node != None:
            self.inOrder (node.left)
            print node.key
            self.inOrder (node.right)

    def printLeft (self, node):
        if node != None:
            self.printLeft (node)
            print node.key

    def debugAll (self):
        self.inOrder (self.root)
        #self.printLeft (self.root)

    def fromArray (self, numbers):
        srt = sorted(numbers)
        print srt
        length = len(srt)
        mid = length/2
        rootEle = srt[mid]
        self.insertKey (rootEle)
        for i in range (1, mid+1):
            try:
                #pdb.set_trace()
                self.insertKey (srt[mid-i])
                self.insertKey (srt[mid+i])
            except IndexError:
                pass

bst = BST()
bst.fromArray ([1,2,4,3,6,5,10,8,9])
bst.debugAll ()

However the result of the inOrder tree walk is unexpected

1
4
5
6
10

I tried to debug through the pdb while inserting the keys, the keys are properly inserted, but when transversing the tree, some Node are skipped because they're marked as 'NoneType'. May be I am missing out on some language specifics here.

Answer 1

For a start, the code you have below isn't right:

        while (node.left != None and node.right != None):
            if node.key < key:
                node = node.right
            else:
                node = node.left

It will stop descending if either the left or the right node doesn't exist.

EDIT: If you modify the loop like this, it works. Could be better optimized, but it's a start...

class Node():
    def __init__(self, parent=None, key=None):
        self.parent = parent if parent != None else None
        self.left = None
        self.right = None
        self.key = key if key != None else None

class BST():
    def __init__(self):
        self.root = Node()

    def insertKey (self, key):
        #pdb.set_trace()
        # transverse till we find empty position
        if (self.root.key == None):
            self.root.key = key
        else:
            node = self.root
            while 1:
                if node.key < key:
                    if node.right is None:
                        node.right = Node(node, key)
                        break
                    else:
                        node = node.right
                else:
                    if node.left is None:
                        node.left = Node(node, key)
                        break
                    else:
                        node = node.left

    def inOrder (self, node):
        #pdb.set_trace()
        if node != None:
            self.inOrder (node.left)
            print node.key
            self.inOrder (node.right)

    def printLeft (self, node):
        if node != None:
            self.printLeft (node)
            print node.key

    def debugAll (self):
        self.inOrder (self.root)
        #self.printLeft (self.root)

    def fromArray (self, numbers):
        srt = sorted(numbers)
        print srt
        length = len(srt)
        mid = length/2
        rootEle = srt[mid]
        self.insertKey (rootEle)
        for i in range (1, mid+1):
            try:
                #pdb.set_trace()
                self.insertKey (srt[mid-i])
                self.insertKey (srt[mid+i])
            except IndexError:
                pass

bst = BST()
bst.fromArray ([1,2,4,3,6,5,10,8,9])
bst.debugAll ()