Binary Search Tree, Logical and Syntax Error

Question

I am trying to implement a binary search tree, But I think I did a logical and syntax error, brain fart now.

I Implemented the basic operations following a Pseudo code I have (I cannot refactor the code). What I have implemented so far is class find, findMax, Insert, Traverse, But looks like I am doing a logical mistake somewhere, any help ?

#!/usr/bin/python3.6

class Node:
  def __init__(self, key=None):
    self.key = key
    self.left = None
    self.right = None

class BST:
  root = Node()

  def find0(self, key):
    x =  self.find(self.root, key)
    return x

  # Recusive
  def find(self, root, key):
    if root is None or key == self.root.key:
      return self.root
    elif key > self.root.key:
      return self.find(self.root.right, key)
    else:
      return self.find(self.root.left, key)

  def findMin0():
    FNode = self.findMin(self.root)
    return FNode

  # Recursive
  def findMin(self, root):
    if self.root.right is None:
      return self.root
    else:
      return findMin(self.root.left)

 def findMax0():
    FNode = findMin(self.root)
    return FNode

  # Recursive
  def findMax(self, root):
    if self.root.right is None:
      return self.root
    else:
      return findMin(self.root.left)

  def insert(self, data):
    self.root = self.insertInTree(self.root, data)

  def insertInTree(self, root, key):
    if root.left is None and root.right is None :
       root = Node(key)
       return root
    elif key < root.key:
       root.left = self.insertInTree(root.left, key)
    elif key > root.key:
       root.right = self.insertInTree(root.right, key)
    return root

  def traverseInOrder0(self):
    self.traverseInOrder(self.root)

  def traverseInOrder(self, root):
    if root.key is not None:
      self.traverseInOrder(root.left)
      self.visit(root)
      self.traverseInOrder(root.right)

  def visit(self, node):
    print (node.key)

  def getRoot():
    return root

def main():
  NewTree = BST()
  NewTree.insert(100)
  NewTree.insert(90)
  NewTree.insert(110)
  NewTree.traverseInOrder0()
  #NewTree.findMin()


if __name__ == "__main__":
  main()

As of now, I can see the following errors

Traceback (most recent call last):  
  File "./bst", line 86, in <module>  
    main()  
  File "./bst", line 81, in main  
    NewTree.traverseInOrder0()  
  File "./bst", line 61, in traverseInOrder0  
    self.traverseInOrder(self.root)  
  File "./bst", line 65, in traverseInOrder  
    self.traverseInOrder(root.left)  
  File "./bst", line 64, in traverseInOrder  
    if root.key is not None:  
AttributeError: 'NoneType' object has no attribute 'key'

Answer 1

For one thing you're calling class methods like they are standalone functions. e.g:

    def findMax0():
        FNode = findMin(self.root)
        return FNode

should be:

    def findMax0(self):
        FNode = self.findMin(self.root)
        return FNode

It's difficult to fully understand the code that you've written because using two classes, BST and Node, creates unnecessary complexity. It seems to have resulted in at least a few errors:

    # Recursive
    def findMin(self, root):
        if self.root.right is None:
            return self.root
        else:
            return findMin(self.root.left)

First of all, it needs to be self.findMin(). Secondly you never actually refer to root (only self.root), so the recursion won't work.

You seem to be switching between a functional and object-oriented approach in your recursive code, when it would be much simpler to pick one style. For example, just implementing find() as a method of Node where it probably belongs:

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None

    def find(self, key):
        if key == self.key:
            return self
        if key > self.key and self.right:
            return self.right.find(key)
        if key < self.key and self.left:
            return self.left.find(key)

As you can see the advantage of using a single class is that the objects it contains also have the find() method, so we can call recursively on child nodes.

Answer 2

There are several problems.

This insert function will always replace the root, and never actually insert anything new:

  def insertInTree(self, root, key):
    if root.left is None and root.right is None :
       root = Node(key)
       return root
    ...

Because, in the beginning, root has no children, so this if condition is taken, replacing root with a new node. Since the new node has no children, when you call this function again to insert another value, it will again find that root has no children, and then replace root. It always just replaces root, it will never insert anything new.

Another problem is in traversing:

  def traverseInOrder(self, root):
    if root.key is not None:
      self.traverseInOrder(root.left)
      self.visit(root)
      self.traverseInOrder(root.right)

When is the key ever None? It should be never. A node should always have key. On the other hand, the left and right children may be None. The recursive call leads to the exception in your question. For example, when root.left is None, the call to self.traverseInOrder(root.left) will lead to evaluating if root.key is ..., but root is None, resulting in the exception in your question.

There are probably other problems too, at this point I stopped reading. I suggest to study the pseudo-code deeper.

Answer 3

The traverseInOrder method descends into root.left and root.right unconditionally if root.key is set. If either one of those lacks a key member (e.g. because they're None), then you'll fail. To avoid this, traverseInOrder should either abort at the very top if root is None or only descend into the children if they're not None.