Im working on a BST class implementation in py. Unfortunately my height method is not providing the correct result. When trying t1.height() I get a result of 3 instead of 4 as expected. I suspect part of the problem maybe the termination conditions of the recursion, particularly self.right/left == None check. However, I have to do this since calling height() on a None leaf will result in an error since None is not yet an instance of Node...
class Node:
# Implement a node of the binary search tree.
# Constructor for a node with key and a given parent
# parent can be None for a root node.
def __init__(self, key, parent = None):
self.key = key
self.parent = parent
self.left = None # We will set left and right child to None
self.right = None
# Make sure that the parent's left/right pointer
# will point to the newly created node.
if parent != None:
if key < parent.key:
assert(parent.left == None), 'parent already has a left child -- unable to create node'
parent.left = self
else:
assert key > parent.key, 'key is same as parent.key. We do not allow duplicate keys in a BST since it breaks some of the algorithms.'
assert(parent.right == None ), 'parent already has a right child -- unable to create node'
parent.right = self
# Utility function that keeps traversing left until it finds
# the leftmost descendant
def get_leftmost_descendant(self):
if self.left != None:
return self.left.get_leftmost_descendant()
else:
return self
# TODO: Complete the search algorithm below
# You can call search recursively on left or right child
# as appropriate.
# If search succeeds: return a tuple True and the node in the tree
# with the key we are searching for.
# Also note that if the search fails to find the key
# you should return a tuple False and the node which would
# be the parent if we were to insert the key subsequently.
def search(self, key):
#print("entering search key= ",key," from node= ",self.key)
if self.key == key:
return (True, self)
# your code here
elif self.key == None:
return (False, self)
elif key < self.key:
#print('searching left')
if self.left == None:
return (False, self)
else:
return self.left.search(key)
elif key > self.key:
#print('searching right')
if self.right == None:
return (False, self)
else:
return self.right.search(key)
#TODO: Complete the insert algorithm below
# To insert first search for it and find out
# the parent whose child the currently inserted key will be.
# Create a new node with that key and insert.
# return None if key already exists in the tree.
# return the new node corresponding to the inserted key otherwise.
def insert(self, key):
# your code here
# search for the spot to insert to
if self.search(key)[0] == True:
#print('key already exists')
return None
else:
return Node(key, self.search(key)[1])
# TODO: Complete algorithm to compute height of the tree
# height of a node whose children are both None is defined
# to be 1.
# height of any other node is 1 maximum of the height
# of its children.
# Return a number that is th eheight.
def height(self):
# your code here
if self == None:
return 1
elif self.right == None:
return 1
elif self.left == None:
return 1
leftheight = self.left.height()
rightheight = self.right.height()
return max(leftheight, rightheight) 1
t1 = Node(25, None)
t2 = Node(12, t1)
t3 = Node(18, t2)
t4 = Node(40, t1)
print('-- Testing basic node construction (originally provided code) -- ')
assert(t1.left == t2), 'test 1 failed'
assert(t2.parent == t1), 'test 2 failed'
assert(t2.right == t3), 'test 3 failed'
assert (t3.parent == t2), 'test 4 failed'
assert(t1.right == t4), 'test 5 failed'
assert(t4.left == None), 'test 6 failed'
assert(t4.right == None), 'test 7 failed'
# The tree should be :
# 25
# /\
# 12 40
# /\
# None 18
#
print('-- Testing search -- ')
(b, found_node) = t1.search(18)
assert b and found_node.key == 18, 'test 8 failed'
(b, found_node) = t1.search(25)
assert b and found_node.key == 25, 'test 9 failed -- you should find the node with key 25 which is the root'
(b, found_node) = t1.search(26)
assert(not b), 'test 10 failed'
assert(found_node.key == 40), 'test 11 failed -- you should be returning the leaf node which would be the parent to the node you failed to find if it were to be inserted in the tree.'
print('-- Testing insert -- ')
ins_node = t1.insert(26)
assert ins_node.key == 26, ' test 12 failed '
assert ins_node.parent == t4, ' test 13 failed '
assert t4.left == ins_node, ' test 14 failed '
ins_node2 = t1.insert(33)
assert ins_node2.key == 33, 'test 15 failed'
assert ins_node2.parent == ins_node, 'test 16 failed'
assert ins_node.right == ins_node2, 'test 17 failed'
print('-- Testing height -- ')
print('height t1= ',t1.height())
assert t1.height() == 4, 'test 18 failed'
assert t4.height() == 3, 'test 19 failed'
assert t2.height() == 2, 'test 20 failed'
CodePudding user response：
The standard definition of height (as a function, not a method) is
def height(node):
if node == None:
return 0
else:
return 1 max(height(node.left), height(node.right))
Note that node is an argument, so that you easily handle the "empty" case.
In the case of your code, if node.left is None, then you want to return 1 height(node.right). Likewise for if node.right is None.
CodePudding user response：
def height(self):
# your code here
if self == None:
return 0
elif self.right == None and self.left == None:
return 1
elif self.left == None:
return 1 self.right.height()
elif self.right == None:
return 1 self.left.height()
leftheight = self.left.height()
rightheight = self.right.height()
return max(leftheight, rightheight) 1