curriculum/challenges/english/blocks/learn-tree-traversal-by-building-a-binary-search-tree/65cb45d130c97cb459439fac.md
To find the smallest value in the right subtree, you need to iterate through the left children of the given node until you reach the leftmost (smallest) node in the subtree.
To do this, write a while loop that runs when node.left is not None and move pass inside the while block. This condition checks if there is a left child. As long as there is a left child, the loop continues and there is a smaller value to be found.
you should remove the pass keyword from the _min_value method.
({
test: () => {
assert.isFalse(
runPython(
`_Node(_code).find_class("BinarySearchTree").find_function("_min_value").has_pass()`
)
);
},
});
You should use the condition node.left is not None in the while loop.
({ test: () => assert.match(code, /while\s+node\.left\s+is\s+not\s+None\s*:/) })
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):
pass
--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))