CSC403: Tree code: Recursion going left and right [9/29] Previous pageContentsNext page

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

Computation of the size happens as we go forward, in a preorder traversal.

Initial value of sz at each node is the number of nodes that precede this one in a preorder traversal.

The initial value of sz does not include the node x.

Final value of sz is the initial value plus the size of the tree rooted at x: size (x, sz) returns size (x) + sz

Previous pageContentsNext page