Code review request: rank of a tree node
simpleprogrammer
89

First question here, so not really sure if this is the right section of the Discuss forum for this.

I was implementing the rank of a tree node myself, and I didn't code it using the recursive solution that's widely used. So here's what I implemented. Do you see any issues here?

	public int rank(K key) {
	    // Basic idea: rank(key) = size(parent.left) + size(key.left)
		Node parent = null;
		Node node = root;
		if (node == null) {
			return -1;
		}
		
		while (node != null) {
			int cmp = node.key.compareTo(key);
			if (cmp == 0) {
				int parentSize = parent == null ? 0 : size(parent.left);
				return size(node.left) + parentSize;
			} else if (cmp < 0) {
				parent = node;
				node = node.left;
			} else {
				parent = node;
				node = node.right;
			}
		}
		
		// key not found.
		return -1;
	}
Comments (0)