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