Learn

Recall that a Binary Search Tree provides a fast and efficient way to store and retrieve values. Like with `.insert()`, the procedure to retrieve a tree node by its value is recursive. We want to traverse the correct branch of the tree by comparing the target value to the current node’s value.

The base case for our recursive method is when the target value matches the value of the current node, in which case we would return the current node. The recursive step is for the method to call itself from an existing left child if the target value is less than the root’s value, or from an existing right child if the target value is not less than the root’s value. If none of the previous cases apply, the target value is not found, in which case we would return `None`.

The pseudocode for this procedure is as follows:

``````If target value is the same as the current node value
Return the current node
Else if there is a left child node and target value is less than the root node's value
Recursively search from the left child node
Else if there is a right child node and target value is greater than or equal to the root node's value
Recursively search from the right child node
Else
Return None``````

Given the following tree:

``````        100
/   \
50    125
/  \
25  75``````

To retrieve 75, the algorithm would proceed as follows. For each step, an arrow will point at the node being processed.

``````At the root node, 75 < 100 so we recursively search on the left child if it exists

==> 100
/   \
50    125
/  \
25  75

At node 50, 75 > 50 and there is a right child so we recursively search on the right child

100
/   \
==> 50    125
/  \
25  75

At the node 75, the value matches 75 so return this node

100
/   \
50    125
/  \
25  75 <==``````

Let’s get to implementing the `.get_node_by_value()` method in `BinarySearchTree`! Just like `.insert()`, we are assuming we call this method from the root node.

### Instructions

1.

Define a new method, `.get_node_by_value()`, below the `.insert()` method. It should take parameters, `self` and `value`, the value of the node we are searching for.

Since the method is not doing anything yet, fill it with `pass`.

2.

Let’s write the base case. Remove the `pass` statement you added in the previous exercise. Write an `if` statement that compares the target `value` with the root node’s value (`self.value`). If they are the same we have found the target node, so we return the node, `self`.

3.

If the target value cannot be found in the root node, we want to navigate further down the Binary Search Tree. We start with the `left` child node if it exists and recursively search in the left subtree. To traverse the left tree, we need to make sure the target value is less than the root node’s value.

Write an `elif` statement that checks:

• if the `left` child node exists AND
• if the target value is less than `self.value`

Inside the `elif` block, return with a call to the `.get_node_by_value()` method from the `left` child node, passing in `value`.

4.

Next, we want to implement the recursive step for the right child node if it exists. If the target value is greater than or equal to its value, it must be on the right side.

Write an `elif` statement that checks:

• if the `right` child node exists AND
• if the target value is greater than or equal to `self.value`

Inside the `elif` block, return with a call to the `.get_node_by_value()` method from the `right` child node, passing in `value`.

5.

If none of the previous conditions are `True`, then the target value does not exist in the Binary Search Tree. In this case, we should return `None`.

Create an `else` block that returns `None`.

6.

Let’s check that the method works.

At the bottom of the code, search for the value `75` in the `BinarySearchTree` object already created for you, then display the `value` of the returned tree node using `print()`.

Write another line of code under the previous `print()` statement to search for a non-existent value of `55` in the same `BinarySearchTree` object and print the returned node itself (not its `value`) which should equal to `None`.