Please use the picture provided to add the following methods to the BinarySearchTree class in python:

# Each node of the tree stores data, a left child, and a right child.

# The children are initialized to None when the node is first created.

class Node:

def $\_\_$init$\_\_($self$,$ new$\_$data$)$:

self.data $=$ new$\_$data

self.left $=$ None

self.right $=$ None

class BinarySearchTree:

# The tree keeps track of its root node. An empty tree has root pointing

# to None.

def $\_\_$init$\_\_($self$)$:

self.root $=$ None

# Wrapper method for an in$-$order traversal $-$ this just calls the recursive

# helper method starting from the root of the tree

def in$\_$order$\_$traversal$($self$)$:

print$(\text{'}$In$-$order traversal:$\text{'})$

self.in$\_$order$\_$traversal$\_$helper$($self$.$root$)$

# Recursive helper method for in$-$order traversal

def in$\_$order$\_$traversal$\_$helper$($self$,$ which$\_$node$)$:

# Implicit base case is when which$\_$node is None $-$ do nothing in that

# case

if which$\_$node:

self.in$\_$order$\_$traversal$\_$helper$($which$\_$node.left$)$

print$($which$\_$node.data$)$ # Visit which$\_$node

self.in$\_$order$\_$traversal$\_$helper$($which$\_$node.right$)$

# Returns a visual representation of the tree

# $($This is a wrapper for the recursive str$\_$helper method$)$

def $\_\_$str$\_\_($self$)$:

return self.str$\_$helper$($self$.$root, $\text{'}-\text{'})$

# This method returns a visual representation of the subtree whose root is

# at which$\_$node. The indent parameter keeps track of how much to indent

# each level.

def str$\_$helper$($self$,$ which$\_$node, indent$)$:

if not which$\_$node:

return 'None'

else:

# The backslashes at the end of each line allow us to split this

# long expression over multiple lines

return str$($which$\_$node.data$)+\text{'}$

$\text{'}+\backslash$

indent $+$ self.str$\_$helper$($which$\_$node.left, indent $+\text{'}-\text{'})+\text{'}$

$\text{'}+\backslash$

indent $+$ self.str$\_$helper$($which$\_$node.right, indent $+\text{'}-\text{'})$

# Add new$\_$data to the tree

def add$($self$,$ new$\_$data$)$:

# Create a new node that contains new$\_$data

new$\_$node $=$ Node$($new$\_$data$)$

# If the tree is currently empty, make new$\_$node the root

if not self.root: # Same thing as self.root $==$ None

self.root $=$ new$\_$node

# If tree is not empty, start from the root and search down the tree

# until an available spot is found

else:

temp $=$ self.root

while True:

if new$\_$data $$ temp.data: # Go left down the tree

# If there's space on the left, insert new$\_$node to the left

if not temp.left: # Same thing as temp.left $==$ None

temp.left $=$ new$\_$node

break

# If there's not space on the left, move left

else:

temp $=$ temp.left

else: # Go right down the tree

# If there's space on the right, insert new$\_$node to the right

if not temp.right: # Same thing as temp.right $==$ None

temp.right $=$ new$\_$node

break

# If there's not space on the right, move right

else:

temp $=$ temp.right

# Searches the tree for a target. Returns the target from the tree if it

# exists, or None if the target doesn't exist. This is a wrapper for the

# recursive find$\_$helper below.

def find$($self$,$ target$)$:

return self.find$\_$helper$($target$,$ self.root$)$

# Searches the subtree whose root is which$\_$node for the target. Returns

# the target if it exists in that subtree, or None if the target doesn't

# exist.

def find$\_$helper$($self$,$ target, which$\_$node$)$:

# Base case $-$ the target can't exist in an empty subtree

if not which$\_$node:

return None

# Base case $-$ target found!

elif target $==$ which$\_$node.data:

return target

# Recursively search which$\_$node's left subtree

elif target $$ which$\_$node.data:

return self.find$\_$helper$($target$,$ which$\_$node.left$)$

# Recursively search which$\_$node's right subtree

else:

return self.find$\_$helper$($target$,$ which$\_$node.right$)$