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 NoneGiven the following tree:
100
/ \
50 125
/ \
25 75To 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
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.
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.
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
leftchild 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.
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
rightchild 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.
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.
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.