Trees

imposes regularity on how hierarchical values are structured and manipulated

Characteristics:

• recursive:

  • a tree has a root and a list of branches

  • each branch is a tree

  • a tree with zero branches is a leaf

• relative:

  • each location in a tree is called a node

  • each node has a label value

  • a node can be the parent/child of another

  • exactly 1 path between 2 nodes

Tree processing

• the base case is often the smallest version of the problem - a leaf

• the recursive call happens on smaller subproblems, which tend to be the branches

• we use the recursive call with some type of aggregation afterwards to get our final solution.