CSC301: Tree code: Deriving non-nullable code from a loop [56/56]

    public int size () {
        if (root == null) return 0;
        return size (root, 1);
    }
    private static int size (Node x, int sz) {
        if (x.left != null) sz = size (x.left, sz + 1);
        if (x.right != null) sz = size (x.right, sz + 1);
        return sz;
    }

This is what you get if you start with a variant of the loop sizeLeft.

Recall the original code. Here, you count the node referenced by x.

    public int sizeLeft () {
        Node x = root;
        int sz = 0;
        while (x != null) {
            x = x.left;
            sz = sz + 1;
        }
        return sz;
    }

In the following variant, we assume that x is already taken care of, and you work on x.left instead.

    public int sizeLeft () {
        if (root == null) return 0;
        Node x = root;
        int sz = 1;
        while (x.left != null) {
            x = x.left;
            sz = sz + 1;
        }
        return sz;
    }

Note that x is non-nullable. It hangs back one place.

Going recursive.

    public int sizeLeft () {
        if (root == null) return 0;
        return sizeLeft (root, 1);
    }
    private static int sizeLeft (Node x, int sz) {
        if (x.left != null) {
            sz = sizeLeft (x.left, sz + 1);
        }
        return sz;
    }

Left and right.

    public int size () {
        if (root == null) return 0;
        return size (root, 1);
    }
    private static int size (Node x, int sz) {
        if (x.left != null) sz = size (x.left, sz + 1);
        if (x.right != null) sz = size (x.right, sz + 1);
        return sz;
    }