I'm trying to build a binary search tree library and I'm getting a syntax error on my piece of code:
class Node:
"""
Tree node: Left and Right child + data which can be any object
"""
def __init__(self,data):
"""
Node constructor
"""
self.left = None
self.right = None
self.data = data
def insert(self,data): # self --> object self.data
"""
Insert new node with data
"""
if data < self.data: # insert data less than current root
if self.left is None: # if left node is empty,
self.left = Node(data) # object left --> Node with new data
else:
self.left.insert(data) # if left node is not empty, go insert again
else:
if self.right is None: # insert data greater than current node
self.right = Node(data) # object right --> Node with new data
else:
self.right.insert(data) # if not empty, run insert again
def lookup(self, data, parent = None):
"""
Lookup node containing data
"""
if data < self.data:
if self.left is None:
return None, None
return self.left.lookup(data,self)
elif data > self.data:
if self.right is None:
return None, None
return self.right.lookup(data,self)
else:
return self, parent
def delete(self, data):
"""
delete node containing data
"""
""" no child """
if children_count == 0:
# if node has no children, remove it
if parent.left is node: # if parent is pointing to current node
parent.left = None # set parent pointing left to None
else:
parent.right = None # else set parent pointing right to None
del node # del node
""" 1 child """
elif children_count == 1:
# if node has 1 child
# replace node by it's child
if node.left:
n = node.left
else:
n = node.right
if parent:
if parent.left is node:
parent.left = n
else:
parent.right = n
del node
""" 2 children """
else:
# if node has 2 children
# find its successor
parent = node # parent is equal to current node target of deletion
successor = node.right # successor is right of the node
while successor.left:
parent = successor
successor = successor.left
# replace node data by its successor data
node.data = successor.data
#fix successor's parent's child
if parent.left == successor:
parent.left = successor.right
else:
parent.right = successor.right
def children_count(self):
""" Return the number of children """
if node is None:
return None
cnt = 0
if self.left:
cnt += 1
if self.right:
cnt += 1
return cnt
# method to print tree in order. Use recursion inside print_tree() to walk the tree breath-first
def print_tree(self):
if self.left:
self.left.print_tree()
print self.data,
if self.right:
self.right.print_tree()
the error is:
Traceback (most recent call last):
File "<pyshell#10>", line 1, in <module>
import BSTlib
File "BSTlib.py", line 78
elif children_count == 1:
^
I can't seem to see what is wrong =[ Can someone help me point this out? Thank you!