This lesson walks through the implementation of a Binary Search Tree in Python. This BST stores data, and inserts and retrieves data in O(logN) time.

Binary Search Trees: Python

There are two main ways of traversing a binary tree: breadth-first and depth-first. With breadth-first traversal, we begin traversing at the top of the tree's root node, displaying its value and continuing the process with the left child node and the right child node. Descend a level and repeat this step until we finish displaying all the child nodes at the deepest level from left to right. 

With depth-first traversal, we always traverse down each left-side branch of a tree fully before proceeding down the right branch. However, there are three traversal options:  
 - _Preorder_ is when we perform an action on the current node first, followed by its left child node and its right child node
 - _Inorder_ is when we perform an action on the left child node first, followed by the current node and the right child node
 - _Postorder_ is when we perform an action on the left child node first, followed by the right child node and then the current node

For this lesson, we will implement the inorder traversal option. The advantage of this option is that the values are displayed in sorted order from the smallest to the largest value.

To illustrate, let's say we have a binary tree that looks like this:
```pseudo
           15
     /------+-----\
    12            20
   /   \         /   \   
 10     13     18     22
 / \   /  \    / \   /  \
8  11 12  14  16 19 21  25
```

We begin by traversing the left subtree at each level, which brings us to the nodes with values `8`, `10`, and `11`. The inorder traversal would be:
```pseudo
8, 10, 11
```

We ascend one level up to visit root node `12` before we descend back to the bottom where the right subtree of `12`, `13`, and `14` resides.
Inorder traversal then continues with the values:
```pseudo
12, 12, 13, 14
```

We again ascend one level up to visit root node `15` before we traverse the right subtree starting at the bottom level again. We continue with the bottom leftmost subtree where `16`, `18`, and `19` reside. The inorder traversal continues with:
```pseudo
15, 16, 18, 19
```

We ascend one level up to visit root node `20` before we descend back to the bottom where the rightmost subtree containing nodes with values `21`, `22`, and `25` resides.

Traversal finishes with:
```pseudo
20, 21, 22, 25
```

The entire inorder traversal becomes:
```pseudo
8, 10, 11, 12, 12, 13, 14, 15, 16, 18, 19, 20, 21, 22, 25
``` 
Notice that all the values displayed are sorted in ascending order.

Now let's implement this inorder traversal for the `BinarySearchTree` class!

Traversing A Binary Search Tree

When inserting a new value into a Binary Search Tree, we compare it with the root node's value. We will implement an `.insert()` method in the `BinarySearchTree` class, assuming that we call the method from a root node like so:

```py
root_node.insert(new_node)
```

Here’s how insertion will work:

If a new value is less than the current (root) node’s value, we want to insert it to its left subtree.

* If a left child of the current node doesn’t already exist, we create a new `BinarySearchTree` node with that value as this node’s left child. 
* If a left child already exists, we would call `.insert()` recursively on the current node’s left child to insert further down.

If a new value is _not_ less than the current (root) node’s value, we’ll want to insert it as a descendant on the right side. The logic for this will be similar:

* If a right child of the current node doesn’t already exist, we create a new `BinarySearchTree` node with that value as this node’s right child.
* If a right child already exists, we would call `.insert()` recursively on the current node’s right child.

The pseudocode for the insertion procedure is as follows:

```pseudo
If the new value is less than the root node's value
  If a left child node does not exist
    Create a new BinarySearchTree with the new value and updated depth and assign it to the left pointer
  Else
    Recursively call .insert() on the left child node  
Else
  If a right child node does not exist
    Create a new BinarySearchTree with the new value and updated depth and assign it to the right pointer
  Else
    Recursively call .insert() on the right child node
```

Let's illustrate the insertion procedure with a tree whose root node has the data `100`. At each step, an arrow will point at the node being processed.
```pseudo
Insert 50
50 < 100, left child node doesn't exist, create a left child node with value 50 and depth 2

    ==> 100
       /
      50

Insert 125
125 > 100, right child node doesn't exist, create a right child node with value 125 and depth 2

    ==> 100
       /   \
      50    125

Insert 75
75 < 100, left child node with value 50 exists, recursively insert at left child

    ==> 100
       /   \
      50    125

75 > 50, right child node doesn't exist, create a right child node with value 75 and depth 3

        100
       /   \
  ==> 50    125
       \
       75

Insert 25
25 < 100, left child node with value 50 exists, recursively insert at left child

    ==> 100
       /   \
      50    125
        \
        75

25 < 50, left child node doesn't exist, create a left child node with value 25 and depth 3

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

Note that we need to update the `depth` of each inserted node. To do so, we add `1` to the current node’s depth when we insert a node as a left or right child.

Let’s implement this `.insert()` method!

Inserting A Value

In this lesson, you have successfully built a Binary Search Tree (BST) data structure in Python. You have implemented:

 - a `BinarySearchTree` class containing `value`, `depth`, and `left` and `right` child nodes.
 - an `.insert()` method to place a node of a specified value at the correct location in the Binary Search Tree. The time efficiency of this operation is `O(logN)` for a balanced tree - if there are `N` nodes in the BST, the max depth of a balanced tree is `log(N)`. So, this method makes at most `log(N)` value comparisons. In the worst case of an imbalanced tree (all values on one side), the performance would be `O(N)`.
 - a `.get_node_by_value()` method to retrieve a node in the tree by its value. The time efficiency of this operation is also `O(logN)` for a balanced tree - if there are `N` nodes in the BST, the max depth of the tree is `log(N)`, so this method makes at most `log(N)` value comparisons. In the worst case of an imbalanced tree (all values on one side), the performance would be `O(N)`. 
 - a `.depth_first_traversal()` method to print the inorder traversal of the Binary Search Tree. This visits every single node, so if there are `N` nodes, the time efficiency for traversal is `O(N)`.

Great job! The Binary Search Tree is a dynamic data structure that provides efficient insertion and searching of data. It has the benefit of being easily expandable while maintaining a sorted order of the data. In more complex implementations, we could include:
- a `.delete()` method
- a self-balancing feature as data is inserted that maintains that two sides of the tree are even, guaranteeing a max depth of `log(N)`

Try these out for yourself if you are up for the challenge!

Review

A Binary Search Tree is an efficient data structure for fast (`O(log N)`) data storage and retrieval. It is a specialized tree data structure that is made up of a root node, and at most two child branches, or subtrees. 

Depending on the requirements, a Binary Search Tree can have certain qualities. It can allow duplicate values to exist, or enforce that there are unique values only. If duplicate values are allowed, it must be decided whether nodes with equal value go on the root's left subtree or right subtree. 

For this implementation, duplicate values will be allowed, and nodes with values that are the same as the root node's will be in the root node’s right subtree.

Each node will be an instance of the `BinarySearchTree` class and will have the following properties:

* a value that represents the data stored
* a depth, where a depth of `1` indicates the top level, or root, of the tree and a depth greater than `1` is a level somewhere lower in the tree
* a left instance variable that points to a left child which is itself a Binary Search Tree, and must have a data lesser than its parent node's data
* a right instance variable that points to a right child which is itself a Binary Search Tree, and must have a data greater than or equal to its parent node's data

![Sample Binary Tree](https://content.codecademy.com/courses/updated_images/Binary_Search_Tree_Visualization_Updated_1.svg)

In the following exercises, we will be implementing a Binary Search Tree in Python. Each Binary Search Tree node will have the instance variables `data`, `depth`, `left` and `right`, and methods for insertion, retrieval, and traversal of the tree. Let's get started!

Introduction

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:

```pseudo
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:

```pseudo
        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.

```pseudo
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.