Lesson 11

Trees (and rooted trees especially) have many applications not only in graph theory, but also in many other branches of mathematics and computer science. We give a number of examples below.

• Data structures.  Many data structures are tree-based: search trees, heaps, segment trees, suffix trees, disjoint-set trees. Below we show a search tree for a set of integer keys.

  



• Algorithms.  Many algorithms build or traverse a tree (that is either stored explicitly or is constructed on the fly): depth-first tree, breadth-first tree, spanning tree, backtracking, branch-and-bound, alpha–beta pruning. Below, we show a backtracking tree for the \(4\) Queens problem.
  

  



• Recursion tree.  A recursion tree shows the execution flow of a recursive function. For example, a call to \(\texttt{fib}(4)\) results in the following tree of recursive calls.

  def fib(n):
      return n if n <= 1 else fib(n - 1) + fib(n - 2)

  
  

  



• Expression tree.  Trees are a convenient way to represent the structure of texts, programs, and expressions. Below is the tree of an expression \[5-((8+7) \times (4-(8+9))).\]
  

  



• Decision tree.  Decision trees are used in many branches of computer science such as machine learning and operations research. Below, we show a decision tree that allows one to sort three elements \(a_{1},a_{2},a_{3}\) by a few pairwise comparisons.