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.$\text{'}$

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$)$:

if self.key $==$ key:

return $($True$,$ self$)$

# your code here

elif key $<$ self.key and self.left:

return self.left.search$($key$)$

elif key $>$ self.key and self.right:

return self.right.search$($key$)$

else:

return $($False$,$ self$)$

#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

$($found$,$ node$)=$ self.search$($key$)$

if found:

return None

else:

return Node$($key$,$ node$)$

# 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.left is None and self.right is None:

return $1$

elif self.left is None:

return $1+$ self.right.height$()$

elif self.right is None:

return $1+$ self.left.height$()$

else:

The code above does not pass to delete $18$ with recursion error

# Testing deletion

t$1=$ Node$(16,$ None$)$

# insert the nodes in the list

lst $=[18,25,10,14,8,22,17,12]$

for elt in lst:

t$1.$insert$($elt$)$

# The tree should look like this

# $16$

# $/\backslash$

# $1018$

# $/\backslash /\backslash$

# $8141725$

# $//$

# $1222$

# Let us test the three deletion cases.

# case $1$ let's delete node $8$

# node $8$ does not have left or right children.

t$1.$delete$(8)$ # should have both children nil.

$($b$8,$n$8)=$ t$1.$search$(8)$

assert not b$8,$ 'Test A: deletion fails to delete node.$\text{'}$

$($b$,$n$)=$ t$1.$search$(10)$

assert$($ b$),$ 'Test B failed: search does not work'

assert n$.$left $==$ None, 'Test C failed: Node $8$ was not properly deleted.$\text{'}$

# Let us test deleting the node $14$ whose right child is none.

# n is still pointing to the node $10$ after deleting $8.$

# let us ensure that it's right child is $14$

assert n$.$right $!=$ None, 'Test D failed: node $10$ should have right child $14\text{'}$

assert n$.$right.key $==14,$ 'Test E failed: node $10$ should have right child $14\text{'}$

# Let's delete node $14$

t$1.$delete$(14)$

$($b$14,$ n$14)=$ t$1.$search$(14)$

assert not b$14,$ 'Test F: Deletion of node $14$ failed $--$ it still exists in the tree.$\text{'}$

$($b$,$n$)=$ t$1.$search$(10)$

assert n$.$right $!=$ None $,$ 'Test G failed: deletion of node $14$ not handled correctly'

assert n$.$right.key $==12,$ f'Test H failed: deletion of node $14$ not handled correctly: $\{$n$.$right.key$\}\text{'}$

# Let's delete node $18$ in the tree.

# It should be replaced by $22.$

t$1.$delete$(18)$

$($b$18,$ n$18)=$ t$1.$search$(18)$

assert not b$18,$ 'Test I: Deletion of node $18$ failed'

assert t$1.$right.key $==22,\text{'}$ Test J: Replacement of node with successor failed.$\text{'}$

assert t$1.$right.right.left $==$ None, $\text{'}$ Test K: replacement of node with successor failed $--$ you did not delete the successor leaf properly?$\text{'}$

print$(\text{'}--$ All tests passed: $15$ points!$--\text{'})$