# David J Nevin+= Code

Last updated: Jun 27, 2022

# 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.

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

 ``````100 101 102 103 104 105 106 107 108 109 `````` ``````class Node(object): def __init__(self, data): self.data = data self.left = None self.right = None class BST(object): def __init__(self, root): self.root = Node(root) ``````
Algorithm Average Case Worst Case
Search O(logn) O(n)
Insert O(logn) O(n)
Delete O(logn) O(n)

note:

 ``````100 101 102 103 104 `````` ``````| Algorithm | Average Case | Worst Case | | :-------: | :----------: | :--------: | | Search | O(_logn_) | O(n) | | Insert | O(_logn_) | O(n) | | Delete | O(_logn_) | O(n) | ``````

Next: Site Projects June 19th
Previous: Level Order Traversal Binary Tree