A binary search tree is a data structure that store data in a manner that is optimized for searching. This data structure is suitable for storing objects that have a well established order and are comparable.

A binary search tree is a binary tree in which the arrangement of the nodes satisfies the following properties:

- Each node has at most two children,
**left**child and**right**child. - Values stored in the left subtree of a node(
`n`

) are smaller than the value of`n`

. - Values stored in the right subtree of a node(
`n`

) are larger than the value of`n`

.

The following figure shows a binary search tree.

If you observe the above figure, you will see that for every node, the left subtree has smaller values while the right subtree has larger values. This property makes it possible to perform efficient search operations.

Consider if we want to search for the node with a value of `7`

in the tree shown in the previous figure. We would follow the path shown by the figure below.

The search starts at the root node, at each step the value is compared with the value of the current node. If the value is smaller, the algorithm moves to the left child. If the value is larger, the algorithm moves to the right child. This process continues until the value is found or there are no more nodes to search.

The time complexity for searching in a binary search tree is` O(log n)`

, where `n`

is the number of nodes in the tree. This is because at each step, the search space is divided in half, dramatically reducing the number of comparisons needed to find the value.

## Implementing Binary Search Trees

Binary search trees are simply binary trees in which the aforementioned properties are upheld.

Python does not provide a builtin implementation of the tree data structure, users can implement trees from scratch or use third-party libraries. In this article, we will use the `binarytree`

package to create binary trees.

The `binarytree `

module is suitable for educational purposes, in real applications, you may implement your own binary trees or use other third party libraries.

To install `binarytree`

, use the following pip command.

`pip install binarytree`

The `binarytree `

module provides the `Node `

class to represent a node in a tree. To instantiate a node, we use the following syntax:

`Node(value, left = None, right = None)`

`value` |
The object held by the node. |

`left` |
The left child of the node. Should be an instance of the `Node ` class. |

`right` |
The right child of the node. Should be an instance of the `Node ` class |

### Create a binary search tree

Creating a binary search tree

```
from binarytree import Node
root = Node(10)
n1 = Node(6)
n2 = Node(14)
root.left = n1
root.right = n2
n3 = Node(4)
n4 = Node(8)
n1.left = n3
n1.right = n4
print(root)
print(root.is_bst) #check whether the tree is a binary search tree
```

Creating the nodes manually as in above example can be very tedious especially if the tree contains a lot of nodes. We can instead use, the `build()`

function in the module to create a binary tree from an iterable such as a list.

The` build()`

function has the following syntax:

`build(iterable)`

The values in the iterable should be given in breadth-first order

```
from binarytree import build
values = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13]
T = build(values) #create the tree
print(T)
print(T.is_bst)
```

### Searching for a value

To search for the node that holds a given value, we can recursively traverse through the relevant nodes.

At each node the search algorithm compares the node's value with the value to be searched. If the value being searched is equal to the node's value; the node is returned. If less; the search moves to the left child of the node. If greater; the search moves to the right child.

Implement the search algorithm

```
def search(n, value):
if value == n.value:
return n
elif value < n.value and n.left is not None:
return search(n.left, value) #recur on left subtree
elif value > n.value and n.right is not None:
return search(n.right, value) #recur on right subtree
return n #unsuccessiful search
```

Note that in case of an unsuccessful search, we are returning the last node that was visited before the search terminated. This will prove useful when inserting a node in the tree as it indicates the position where the node should have been located if it was present.

Use the search() function

```
from binarytree import build
#the implementation of search() is omitted refer to the previous section
data = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13 ]
T = build(data)
val = 13
n = search(T, val)
if n.value == val:
print(f'found {n}')
else:
print('No such value.')
```

found:

13

In the above example we used the search function to find the node with `13 `

as the value, the path taken by the algorithm to find the node is as illustrated below.

Consider what happens when we search for a value that does not exist. In this case the search function will return the last position where it expected to find the non-existent value.

Find for 7.5 in the tree

```
from binarytree import build
#the implementation of search() is omitted refer to the previous section
data = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13 ]
T = build(data)
val = 8.5
n = search(T, val)
if val == n.value:
print(f'found: {n}')
elif val < n.value:
print(f"{val} should be placed at the left of {n.value}")
else:
print(f"{val} should be placed at the right of {n.value}")
```

7.5 should be placed at the right of 7

### Inserting a value in the tree

When inserting a value in a binary search tree, we must ensure that the binary search tree's structure is maintained so that nodes to the left of a parent node have values smaller than the parent, and all the nodes to the right have larger values.

From the previous section, we have seen that the` search() `

function returns the place where a node should have been if it was present in the tree. We will use the method with the value to be inserted as the argument in order to get the node at which the value will be attached.

```
from binarytree import Node
def insert(T, val):
parent = search(T, val)
if val == parent.val: #the value exists in the tree
return #do nothing
newnode = Node(val)
if val < parent.value: #the value is less than the parent
parent.left = newnode
else: #the value is greater than the parent
parent.right = newnode
```

Use the insert() function

```
from binarytree import build
#implementation of search and insert() is omitte, refer to previous sections
data = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13 ]
T = build(data)
insert(T, 7.5)
insert(T, 6.5)
insert(T, 8.5)
print(T)
```

__________________10_________

/ \

__6__________ ____14

/ \ / \

4 ____8____ _12 15

/ \ / \ / \

3 5 _7_ _9 11 13

/ \ /

6.5 7.5 8.5

## Resulting Properties of Binary Search Trees

One important resulting feature of binary search trees is that the inorder traversal algorithm always yields the elements in a sorted order.

inorder algorithm with a binary search tree

```
from binarytree import build
data = [10, 6, 14, 4, 8, 12, 15, 3, 5, 7, 9, 11, 13]
T = build(data)
print(*[i.value for i in T.inorder], sep = " ")
```