Average | Worst case | |
---|---|---|

Space | O(n) | O(n) |

Search | O(log n) | O(n) |

Insert | O(log n) | O(n) |

Delete | O(log n) | O(n) |

Properties

Has binary tree properties:

- Collection of nodes
- Each node has at most two children, left and right

Along with the following added properties:

- Ordered, the left subtree contains only nodes with keys less than the node’s key.
- The right subtree contains only nodes with keys greater than the node’s key.
- Duplicates may or may not be allowed. See dealing with duplicates in a binary search tree.

Common Operations

Insert

Search

Delete

## Tree Traversal

**In-Order Traversal**– left, current, right**Pre-Order Traversal**– current, left, right**Post-Order Traversal**– left, right, current

## Balanced Tree

- A balanced tree refers to how evenly the nodes are distributed.
- Having a balanced tree ensures optimal performance (O(log n)) Search , Insert and Delete
- Common types of balanced trees:
- Red-Black Trees
- AVL Trees

## Types of completeness:

**Complete Binary Tree**– binary tree in which every level is fully filled, except perhaps the last level. To the extent that the last level is filled, it is filled left to right.

**Full Binary Tree**– every node has either zero or two children. That is, no nodes have only one child

**Perfect Binary Tree**– A perfect binary tree is both full and complete. All leaf nodes will be the same level and this level has the maximum number of nodes. Must ave exactly (2^k) – 1 nodes where k is the number of levels.