curriculum/challenges/english/blocks/learn-tree-traversal-by-building-a-binary-search-tree/65d8b58074495d3f94977dca.md
Once the leftmost node is found (that is, when node.left becomes None), the loop exits.
After the while loop, return the key of the leftmost node, which represents the minimum value in the given subtree.
With this, you are able to get the value that will replace the node after it is deleted.
After the while loop, return node.key as the result of the function.
({ test: () => assert.match(code, /^(\s+)while.*:.+?^\1return\s+node\.key/ms) })
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
def __str__(self):
return str(self.key)
class BinarySearchTree:
def __init__(self):
self.root = None
def _insert(self, node, key):
if node is None:
return TreeNode(key)
if key < node.key:
node.left = self._insert(node.left, key)
elif key > node.key:
node.right = self._insert(node.right, key)
return node
def insert(self, key):
self.root = self._insert(self.root, key)
def _search(self, node, key):
if node is None or node.key == key:
return node
if key < node.key:
return self._search(node.left, key)
return self._search(node.right, key)
def search(self, key):
return self._search(self.root, key)
def _delete(self, node, key):
if node is None:
return node
if key < node.key:
node.left = self._delete(node.left, key)
elif key > node.key:
node.right = self._delete(node.right, key)
else:
if node.left is None:
return node.right
elif node.right is None:
return node.left
--fcc-editable-region--
def _min_value(self, node):
while node.left is not None:
node = node.left
--fcc-editable-region--
bst = BinarySearchTree()
nodes = [50, 30, 20, 40, 70, 60, 80]
for node in nodes:
bst.insert(node)
# print('Search for 80:', bst.search(80))