Tutorial 7: Notes

Tree Sum

Write a function that computes the sum of all values in a binary tree of integers.

type
  node = record
    i: integer;
    left: ^node;
    right: ^node;
  end;
  
  pnode = ^node;

function sum(t: pnode): integer;
begin
  if t = nil then exit(0)
  else exit(t^.i + sum(t^.left) + sum(t^.right));
end;

Tree Height

Write a function that returns the height of a binary tree.

uses math;

function height(t: pnode): integer;
begin
  if t = nil then exit(0)
  else exit(1 + max(height(t^.left), height(t^.right)));
end;

Complete Tree

Write a function that returns true if a binary tree is complete, that is, if every leaf has the same depth and all internal nodes have two children.

Here is a first implementation that uses the height function from the previous exercise:

function complete(t: pnode): boolean;
begin
  if t = nil then exit(true)
  else exit((height(t^.left) = height(t^.right)) and
            complete(t^.left) and complete(t^.right));
end;

If the tree is balanced and has N nodes, the running time of this function follows the recurrence

T(n) = 2 T(n/2) + O(n)

since height runs in linear time. This means that

T(n) = O(n log n)

For a more efficient implementation, we can write a single function that both determines whether a tree is complete and also returns its height if it is complete:

// Return the height of t if it is complete, or -1 otherwise.
function heightComplete(t: pnode): integer;
var
  l, r: integer;
begin
  if t = nil then exit(0)
  else begin
    l := heightComplete(t^.left);
    r := heightComplete(t^.right);
    if (l <> -1) and (r <> -1) and (l = r)
    then exit(l + 1)
    else exit(-1);
  end;
end;

For a balanced tree, this function's running time obeys the recurrence

T(n) = 2 * O(n/2) + O(1)

and so T(n) = O(n).