A Tree is a data structure built of connected nodes much like a linked list. The difference is that nodes can have more than one successor (child) in a Tree. Trees are the underlying structure involved with heaps. They also find use in many graph theory applications and in analyzing recursive functions.

The top node of a tree (the one with no predecessors) is referred to as the root node.

The type of tree that is most commonly used is a binary tree which is a tree with the additional restriction that every node can have at most two children. (The example tree to the right is not a binary tree) One of the most basic types is the binary search tree. In this tree the left child node is always smaller than the parent and the right child node is always larger than the parent. This additional structuring improves the finding operation because when searching for a value you can ignore an entire half of the remaining subtree at each step.

#### Binary Search Tree

Operation | Complexity | Description |
---|---|---|

find | $O(\log n)$ | finds a particular value in the tree |

insert | $O(1)$ | inserts a node at a known location |

remove | $O(1)$ | removes a node at a known location |

#### Unstructured Tree

Operation | Complexity | Description |
---|---|---|

find | $O(n)$ | the entire tree may potentially be searched |

insert | $O(1)$ | inserts a node at a known location |

remove | $O(1)$ | ihserts a node at a known location |