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