curriculum/challenges/english/blocks/learn-tree-traversal-by-building-a-binary-search-tree/65ca07dd6fa8840491b7a5cd.md
If neither one of the previous conditions is met, it means the node has both left and right children.
To choose the successor, you need to find the minimum value in the right subtree. The smallest value will be the in-order successor of the current node.
To find the smallest value, create a helper function _min_value that takes two parameters: self and node.
You should define the _min_value method with self and node as the parameters. Remember to use the pass keyword.
({ test: () => assert.match(code, /def\s+_min_value\(\s*self\s*,\s*node\s*\)\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--
--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))