Trees


Trees have special quality that their nodes can be subtrees. They have self-similar property.  This property can be expressed with "recursive" structure.  The operations on trees can be implemented with recursive programs.  

Recursion

Here is some example of recursive definition of functions.

factorial(n) is 1                  if n == 0
                n * factorial(n-1) otherwise

fac 5 -->
    5 * fac 4
          ----> 4 * fac 3
                       ----> 3 * fac 2
                                   -----> 2 * fac 1
                                                -----> 1 * fac 0
                                                              1

=> 5 * 4 * 3 * 2 * 1 * 1

The number of recursive calls depends on n.  In some function, the number of recursive calls grows much faster than n. Here is an example.

n           1 2 3 4 5 6 7 ...
Fibonacci   1 1 2 3 5 8 13 ...

fib(n) is  1                    if n < 3
           fib(n-2) + fib(n-1)  otherwise

           fib 5
           /     \
         fib 4     fib 3
        /     \     \     \
      fib 3  fib 2  fib 2  fib 1
      
The number of recursive calls grows exponentially in n.

Recursion is fundamental in computer science. Many operations can turned into recursion.  For example, finding the length of a list.

let a be a list

listLen(a)  is   
    if a is nil return 0
    else return 1 + listLen(rest(a))

where rest(a) is the list without the first element.

Or doing a summation of 1..n

sum(n) is  sum2(n, 0)

sum2(n, a) is
    if n == 0  return a
    else return sum2(n-1, a+n)

sum(3) --> sum2(3, 0)

sum2(3,0) --> sum2(2, 3+0) --> sum2(1, 2+3) --> sum2(0, 1+5) --> 6

The style presented here called "a" in sum2(n,a) as "accumulating parameters" (the sum is accumulated there).

Binary trees

Binary tree is a tree with at most two children, called left child and right child.  A "complete binary tree" is a binary tree which has exactly two children at every levels.  The height of a tree is the number of "level" from the "root" to the "leaves" of that tree.

A binary tree with 3 levels has at most 7 nodes.

level 0             .
                   / \
level 1           .   .
                 / \ / \
level 2         .  . .  .

A binary tree with h levels has at most sum i=0..h-1 (2^i)

Operations on trees include:

binary_search(x, t)  is
  if t == nil return FALSE
  if x == t.info return TRUE
  if binary_search(x, t.left) == TRUE return TRUE
  else return binary_search(x, t.right)

Implementation

A node in a tree usually contains one information.  It also has two pointers to its children.
    
    -----------------------
    | left | info | right |
    -----------------------

For example a tree of arithmetic expression  (a + b) - c

           -
          / \
         +   c
        / \
       a   b
         
The fields in a node can be arranged many ways:

    -----------------------
    | info | left | right |
    -----------------------

Alternative implementation

You can use list to implement a tree.  A node of a list consists of two pointers: info, next.

We illustrate it using this notation
.--
|

where | is info and .-- is next  / is nil

Using the previous example  (a + b) - c

      --->  .------------.--.--/
            |            |  |
            .--.--.--/   -  c
            |  |  |
            a  +  b

The structure like  .--.--.--/  is called the "skeleton" or the "spine".
                    |  |  |

Application

Let perform a task of converting a postfix expression into a binary tree.  The input is like  "a b + c -" and the output is a binary tree of arithmetic expression.  We will use a stack to store temporary data.  The algorithm (or the set of rules) to do it is as follows:

read a symbol from the expression one-by-one. For each symbol do:
1  if it is a name then make a node, push it to the stack
2  if it is an operator
   2.1   make a node
   2.2   pop two arguments from the stack
   2.3   link them to left and right of the node
   2.4   push the node to the stack

here we illustrate the work step-by-step:

input "a b + c -"

read "a"  rule 1               a  <-- |  |
                                      ----

read "b"  rule 1               b  <-- |  |
                               a  <-- |  |
                                      ----

read "+"  rule 2             +  <-- |  |
                            / \     ----
                           a   b

and so on...

It can be written in a pseudo code below.  Let e be a postfix expression, S is a stack

postfix_to_tree(e)  is
   while e is not empty
      a = read a symbol from e
      if a is name
          push makeNode(a)
      else if a is operator
          b = makeNode(a)
          b.right = pop
          b.left = pop
          push b
      e = e.next

Homework

The program postfix_to_tree above  used iteration (while). Change it to use recursion.

last update 12 Sept 2008