## 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).