# Binary Search Tree

## Definition

A `binary search tree`

(BST) is a tree data structure in which nodes are arranged according to the following property.

The value of the left child of any node will be less than whatever value in that node, and the value of the right child of the node will be greater than the value in that node.

If there aren’t exactly two children, the reference to the non-existent child will contain null value.

## Search

We employ the same criteria when searching. Starting form the `root`

we decide which branch to search by comparing the search value with the current node. We then traverse the appropriate branch and repeat the process, thus greatly speeding up the search.

## Time Operation

If the tree is non-linear the search time is O(*logn*) and in the worst case where the `tree`

is linear, O(n).

## Implementation

Algorithm | Average Case | Worst Case |
---|---|---|

Search | O(logn) |
O(n) |

Insert | O(logn) |
O(n) |

Delete | O(logn) |
O(n) |

note:

source: Markdown: How to Create a Table