• Must have a root
• Must have directed edges
• Must not have a cycle.

Binary Trees

• Every node has at most two children. (one child is fine.)

Linked list with two next list!

Property

• Height: The number of edges in the longest path from the root to a leaf

• Full: if and only if every node has either zero children or two children.

• Perfect: if and only if all interior nodes have two children and leaves are at the same level.

• Complete: if and only if the tree is perfect up until the last level and all leaf nodes on the last level are pushed to the left

  

Binary Search Trees

Property

• Nodes in the left subtree are less than itself.
• Nodes in the right subtree are greater than itself.

A Binary Search Trees used to implement a dictionary will store both a key and data at every node.

Visiting the longest Path tree or try finding non-exist data: O(log(n))

find