How to override an abstract inner class of an abstract class in their subclasses (kotlin or java)

Question

So basically I have a abstract class representing a BinaryTree below. I want to create a subclass called RBTree which will take advantage of all the abstraction in BinaryTree including the ability to modify the inner Node class to take on a color and parent property.

However I can't figure out how Kotlin or Java do this if they can even at all.

The closest I'm able to come is creating a new class that's a subclass of Node which ruins a lot of the other abstraction in BinaryTree since we have to use different Node objects. Trying to just redefine Node just doesn't work. If you know how to do it in java that would work too.

class RBTree<E : Comparable<E>> : BinaryTree<E>(){
    override val rootNode: RBNode<E> = TODO()

    override fun addNode(node: Node<E>) { //since we have a new class RBNode this doesn't work
        TODO()
    }
    override fun removeNode(): Node<E> { //same problem
        TODO()
    }

    inner class RBNode<E>(data: E, var color: NodeColor, var parent: RBNode<E>?, left: RBNode<E>? = null, right: RBNode<E>? = null) : Node<E>(data, left, right){
        fun switchColor() : NodeColor{
            color = when (color) {
                NodeColor.RED -> NodeColor.BLACK
                else -> NodeColor.RED
            }
            return color
        }
    }

}

enum class NodeColor {
    RED,
    BLACK
}

abstract class BinaryTree<E : Comparable<E>>() {

    abstract val rootNode: Node<E>

    abstract fun addNode(node : Node<E>)

    abstract fun removeNode() : Node<E>

    abstract inner class Node<E : Comparable<E>>(
        private val data: E,
        private val left: Node<E>? = null,
        private val right: Node<E>? = null) : Comparable<Node<E>> {

        fun isLeaf(): Boolean{
            return (left == null && right == null)
        }
        override fun compareTo(other: Node<E>): Int {
            return data.compareTo(other.data)
        }
    }
}

Answer 1

This is not really a limitation of Java or Kotlin. This case is tricky even conceptually. Let's think about it for a while.

We have a common "family" of objects. Then we have a more specialized family which accepts working with their own family only. RBTree doesn't accept working with just any Node, it requires RBNode specifically, for example in addNode(). That means RBTree effectively is not a subtype of BinaryTree, because it can't be used as a BinaryTree.

There are multiple ways to tackle this problem, depending on our specific case.

If we construct the whole graph initially and then we only work with it, but we don't mutate it anymore, then we can separate read-only and mutable interfaces. Only this initial code for constructing the graph will have to make sure RBTree correctly got RBNode. Then RBTree can be safely treated as a read-only BinaryTree and depending if we use RBTree or BinaryTree, we see nodes as either RBNode or Node.

Another approach, very specific to some cases is to adapt Node to be the RBNode. In this solution RBTree allows to add regular Node objects to it, but it wraps them in its own classes and when asked back, it returns a wrapped RBNode. This approach also allows RBTree to be a subtype of the BinaryTree.

Third solution is to parameterize the tree by its node type. We have to introduce N : Node<N, E> in multiple places around the code:

class RBTree<E : Comparable<E>> : BinaryTree<RBNode<E>, E>(){
    override val rootNode: RBNode<E> = TODO()

    override fun addNode(node: RBNode<E>) {
        TODO()
    }
    override fun removeNode(): RBNode<E> {
        TODO()
    }

    class RBNode<E : Comparable<E>>(data: E, var color: NodeColor, var parent: RBNode<E>?, left: RBNode<E>? = null, right: RBNode<E>? = null)
        : Node<RBNode<E>, E>(data, left, right){
        fun switchColor() : NodeColor{
            color = when (color) {
                NodeColor.RED -> NodeColor.BLACK
                else -> NodeColor.RED
            }
            return color
        }
    }
}

abstract class BinaryTree<N : Node<N, E>, E : Comparable<E>>() {

    abstract val rootNode: N

    abstract fun addNode(node : N)

    abstract fun removeNode() : N

    abstract class Node<N : Node<N, E>, E : Comparable<E>>(
        private val data: E,
        private val left: N? = null,
        private val right: N? = null) : Comparable<N> {

        fun isLeaf(): Boolean{
            return (left == null && right == null)
        }
        override fun compareTo(other: N): Int {
            return data.compareTo(other.data)
        }
    }
}

This way we ensure RBTree works with RBNode only. Please note RBTree is no longer a subtype of BinaryTree<Node>. Instead, it is a subtype of BinaryTree<RBNode>.

I removed inner from nodes as it seems this is not needed. If this is in fact required, then the case is a little more complicated, because nodes are implicitly typed by the tree as well.