curriculum/challenges/english/blocks/learn-tree-traversal-by-building-a-binary-search-tree/65ca0d5adf39c410cd1177cc.md
Now, you'll work on traversing the tree based on the in-order traversal method. In-order traversal is a depth-first binary tree traversal algorithm that visits the left subtree, the current node, and then the right subtree.
Define the _inorder_traversal method within the BinarySearchTree class and give it three parameters: self, node and result. Where node is the current node being considered during the traversal and result is the list to which the keys are appended in sorted order.
You should define a method _inorder_traversal that takes three parameters: self, node, and result. Remember to use pass.
assert.match(code, /def\s+_inorder_traversal\(\s*self\s*,\s*node\s*,\s*result\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
node.key = self._min_value(node.right)
node.right = self._delete(node.right, node.key)
return node
def delete(self, key):
self.root = self._delete(self.root, key)
def _min_value(self, node):
while node.left is not None:
node = node.left
return node.key
--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))