Tree

• Node based structure, subset of graphs
  • An Ayclic, Connected Graph, with exactly one Path between any pair of vertices
• A graph is a tree iff it has |V| - 1 edges and is connected or it has |V| - 1 edges and is acyclic
• Parent-child, Ancestor-descendant-sibling Rules

1. Node can have any number of children
2. Node can have 0 or 1 parents
3. Node with 0 parents is the root node
4. All nodes in the tree must be connected / no cycled allowed
   • These statements are equivalent

• Leaf node has no children
• Internal node is any node that is not a leaf
• “Subtree”, self-explanatory

Depth

Height

Varieties

• 2-4 Tree
• Binary Tree
  • Binary Search Tree
  • AVL