Answer:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def search(root, key):
"""
Recursive search operation to find a key in the binary tree.
Returns True if the key is found, False otherwise.
"""
if root is None or root.value == key:
return root is not None
if key < root.value:
return search(root.left, key)
else:
return search(root.right, key)
def insert(root, key):
"""
Recursive insert operation to add a new key to the binary tree.
Returns the updated root node.
"""
if root is None:
return Node(key)
if key < root.value:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def find_min_value_node(node):
"""
Helper function to find the node with the minimum value in a binary tree.
"""
current = node
while current.left is not None:
current = current.left
return current
def delete(root, key):
"""
Recursive delete operation to remove a key from the binary tree.
Returns the updated root node.
"""
if root is None:
return root
if key < root.value:
root.left = delete(root.left, key)
elif key > root.value:
root.right = delete(root.right, key)
else:
if root.left is None:
return root.right
elif root.right is None:
return root.left
# Node with two children: get the inorder successor (minimum value in the right subtree)
min_node = find_min_value_node(root.right)
root.value = min_node.value
root.right = delete(root.right, min_node.value)
return root
# Example usage:
root = None
root = insert(root, 50)
root = insert(root, 30)
root = insert(root, 20)
root = insert(root, 40)
root = insert(root, 70)
root = insert(root, 60)
root = insert(root, 80)
# Search operation
print(search(root, 40)) # Output: True
print(search(root, 90)) # Output: False
# Delete operation
root = delete(root, 30)
print(search(root, 30)) # Output: False
Step-by-step explanation:
In this implementation, a `Node` class is defined to represent each node in the binary tree. It has a `value`, `left`, and `right` attribute to store the value and references to the left and right child nodes.
The `search` function performs a recursive search operation to find a key in the binary tree. It compares the key with the value of the current node and recursively searches the left or right subtree based on the comparison.
The `insert` function performs a recursive insert operation to add a new key to the binary tree. It compares the key with the value of the current node and recursively inserts the key in the left or right subtree based on the comparison. It returns the updated root node.
The `find_min_value_node` function is a helper function to find the node with the minimum value in a binary tree. It is used during the delete operation to find the inorder successor.
The `delete` function performs a recursive delete operation to remove a key from the binary tree. It first searches for the key recursively. If the key is found, it handles three cases: no children, one child, or two children. It then returns the updated root node.
The example usage section demonstrates the usage of these operations by creating a binary tree, performing a search operation, and deleting a node.
Note: This implementation assumes that the binary tree does not contain duplicate keys. It also does not handle balancing the binary tree.