CSC403: Trees: More size

(Click here for one slide per page)

public class IntSet {
    private Node root;
    private static class Node {
        public final int key;
        public Node left, right;
        public Node (int key) { this.key = key; }
    }
    public int size () {
        int size = 0;
        for (int x : this.levelOrder ())
            size++;
       return size;
    }
    ...

This violates two conditions of the assignment.

• calls function other than the recursive helper function
• creates an object. It is indirect via levelOrder, but it creates an object nonetheless, so it violates the condition of the assignment.

public class IntSet {
    private Node root;
    private static class Node {
        public final int key;
        public Node left, right;
        public Node (int key) { this.key = key; }
    }
    int size = 0;
    public int size () {
        for (int x : this.levelOrder ())
            size++;
       return size;
    }
    ...

This now violates yet another criterion of the assignment.

• no fields.

A field is a variable that is declared outside of a method.

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

Is this correct?

Can it be improved?

    public int size() {
        if (root == null) 
            return 0;
        return 1 + size (root);
    }

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

Is this correct?

Can it be improved?

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

Is it correct?

Can it be improved?

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

Is it correct?

Can it be improved?

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

Cleaned up

Counts the number of nulls, rather than the number of nodes.

Correct, but not immediately obvious.

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

Is it correct?

Can it be improved?

    public int size () {
        return size (root);
    }
    private static int size (Node x) {
        int count = 0;
        if (x == null) return 0;
        if (x.left == null && x.right == null) {
            count = 1;
        } else {
            count = 1 + size (x.left) + size (x.right);
        }
        return count;
    }

Is it correct?

Can it be improved?

    public int size () {
        if (root == null) return 0;
        int total = 1 + size (root, 0);
        return total; // do not count self at the start
    }
    private static int size (Node x, int count) {
        // called when it finds the end
        int total = count, left = 0, right = 0; // likely can use less space - see about condensing
        if (x == null) return 0; // return 0 when the node is null - thus finding the end!
        else { // not at the end when this is called
            // if left has more, add them up and return them
            if (x.left != null) {
                left++; // increment
                left += size (x.left, left); // should add...
            }
            if (x.right != null) {
                right++;
                right += size (x.right, right);
            }
            // if right has more, add them up and return them
        }
        total = left + right;
        // return result
        return total;
    }

Is this correct?

Can it be improved?

Get rid of comments:

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

Unnecessary else. Tighten mutators.

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

Get rid of some unnecessary variables and put declaration closer to use.

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

Oops! A bug.

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

Notice that the parameter is not used!

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