findEqualSubtrees for fellaru

findEqualSubtrees.kt

data class TreeNode(
        val value: Char,
        val left: TreeNode? = null,
        val right: TreeNode? = null
)

val tree = TreeNode(
        'a',
        TreeNode('b',
                TreeNode('c'),
                TreeNode('e')
        ),
        TreeNode(
                'b',
                TreeNode('c'),
                TreeNode('e')
        )
)

fun Char.getHash() = 1 shl (this - 'a')

fun TreeNode.getHash(duplicates: MutableSet<TreeNode>, set: MutableSet<Int> = mutableSetOf()): Int {
    // We need to find only one duplicate
    if (duplicates.size > 0) {
        return 0
    }

    val leftHash = left?.getHash(duplicates, set) ?: 0
    val rightHash = right?.getHash(duplicates, set) ?: 0
    val hash = value.getHash() or leftHash or rightHash

    // A leaf is not a subtree!
    if (leftHash == 0 && rightHash == 0) {
        return hash
    }

    if (!set.add(hash)) {
        duplicates.add(this)
    }

    return hash
}

fun TreeNode.findEqualSubtrees(): TreeNode? {
    val duplicates = mutableSetOf<TreeNode>()
    getHash(duplicates)
    return duplicates.firstOrNull()
}

fun main(args: Array<String>) {
    println(tree.findEqualSubtrees())
}