public boolean addLeaf(C leafvalue) {
		if (leafToNode.containsKey(leafvalue))
			return false;
		
		MerkleTree.Node curNode = root;
		
		MerkleTree.Node leafNode = new MerkleTree.Node();
		leafNode.hash = leafvalue;
		leafToNode.put(leafvalue, leafNode);
		
		if (root.left == null) {
			assert root.right == null;
			root.left = leafNode;
			leafNode.parent = root;
			root.leftSubtreeSize = 1;
			root.updateHash();
			depth = 1;
		} else if (root.right == null) {
			root.right = leafNode;
			leafNode.parent = root;
			root.rightSubtreeSize = 1;
			root.updateHash();
		} else {
			/*
			 * Repeatedly choose the child with the smallest subtree until
			 * we reach a leaf.
			 */
			int curdepth = 0;
			while(curNode.leftSubtreeSize > 0) {
				if (curNode.leftSubtreeSize > curNode.rightSubtreeSize)
					curNode = curNode.right;
				else
					curNode = curNode.left;
				++curdepth;
			}
			
			assert curdepth <= depth;
			
			// We've reached a leaf.
			assert curNode.rightSubtreeSize == 0;
			
			// Create a new internal node, and insert it in place of curNode.
			// curNode will become the new left node, and the new leaf will become
			// its new right node.
			MerkleTree.Node newInternal = new MerkleTree.Node();
			newInternal.leftSubtreeSize = newInternal.rightSubtreeSize = 1;
			newInternal.parent = curNode.parent;
			if (curNode.parent.left == curNode) {
				curNode.parent.left = newInternal;
			} else {
				assert curNode.parent.right == curNode;
				curNode.parent.right = newInternal;
			}
			newInternal.left = curNode;
			newInternal.right = leafNode;
			leafNode.parent = curNode.parent = newInternal;
			newInternal.updateHash();
			
			
			if (curdepth == depth)
				++depth; 
			
			// Update the subtree counts and hashes on the path to the root.
			for (curNode = newInternal.parent; curNode != null; curNode = curNode.parent) {
				curNode.leftSubtreeSize = curNode.left.leftSubtreeSize + curNode.left.rightSubtreeSize;
				curNode.rightSubtreeSize = curNode.right.leftSubtreeSize + curNode.right.rightSubtreeSize;
				curNode.updateHash();
			}
		}
		
		return true;
	}