Binary Tree

MutableNode.kt

import java.util.ArrayDeque

fun mutableNode(
    value: Int,
    left: MutableNode? = null,
    right: MutableNode? = null
) = MutableNode(value, left, right)

data class MutableNode(
    val value: Int,
    var left: MutableNode? = null,
    var right: MutableNode? = null
) {

    fun inorderTraversalRecursive(): IntArray = inorderRecursive().toIntArray()

    private fun inorderRecursive(): List<Int> {
        return mutableListOf<Int>().apply {
            left?.run { addAll(inorderRecursive()) }
            add(value)
            right?.run { addAll(inorderRecursive()) }
        }
    }

    fun inorderTraversalNonRecursive(): IntArray {
        val results = mutableListOf<Int>()
        val stack = ArrayDeque<MutableNode>()
        var current: MutableNode? = this
        while (current != null || stack.isNotEmpty()) {
            while (current != null) {
                stack.push(current)
                current = current.left
            }
            current = stack.pop()
            results.add(current.value)
            current = current.right
        }
        return results.toIntArray()
    }

    fun preOrderTraversalRecursive(): IntArray = preorderRecursive().toIntArray()

    private fun preorderRecursive(): List<Int> {
        return mutableListOf<Int>().apply {
            add(value)
            left?.run { addAll(preorderRecursive()) }
            right?.run { addAll(preorderRecursive()) }
        }
    }

    fun postOrderTraversalRecursive(): IntArray = postOrderRecursive().toIntArray()

    private fun postOrderRecursive(): List<Int> {
        return mutableListOf<Int>().apply {
            left?.run { addAll(postOrderRecursive()) }
            right?.run { addAll(postOrderRecursive()) }
            add(value)
        }
    }

    fun preOrderTraversalNonRecursive(): IntArray {
        val results = mutableListOf<Int>()
        val stack = ArrayDeque<MutableNode>()
        var current: MutableNode? = this
        while (current != null || stack.isNotEmpty()) {
            while (current != null) {
                stack.push(current)
                results.add(current.value)
                current = current.left
            }
            current = stack.pop().right
        }
        return results.toIntArray()
    }

    fun postOrderTraversalNonRecursive(): IntArray {
        val pending = ArrayDeque<MutableNode>()
        val processed = ArrayDeque<MutableNode>()
        pending.push(this)
        while (pending.isNotEmpty()) {
            val node = pending.pop()
            node.left?.let { pending.push(it) }
            node.right?.let { pending.push(it) }
            processed.push(node)
        }
        return processed.map { it.value }.toIntArray()
    }

    companion object {
        fun fromRecursive(values: Array<Int?>): MutableNode? {
            return fromRecursive(nodeIndex = 0, values = values)
        }

        /**
         * T = N * (0(1) + O(1) + O(1) + O(1))
         * T = N * 0(1)
         * T = N*c1
         * T = N
         * T = O(N)
         */
        private fun fromRecursive(nodeIndex: Int, values: Array<Int?>): MutableNode? {
            // O(1)
            return values.getOrNull(nodeIndex)?.let { value ->
                // O(1)
                mutableNode(value).apply {
                    // O(1)
                    left = fromRecursive(nodeIndex = nodeIndex * 2 + 1, values = values)
                    // O(1)
                    right = fromRecursive(nodeIndex = nodeIndex * 2 + 2, values = values)
                }
            }
        }

        /**
         * T = O(1) + N*O(1) + N*O(1) + O(1)
         * T = c1 + N*c2 + N*c3 + c4
         * T = 2N*c1
         * T = 2c*N
         * T = O(2N)
         * T = O(N)
         */
        fun fromNonRecursive(values: Array<Int?>): MutableNode? {
            // O(1)
            val nodes = values.map { value ->
                // N * O(1)
                value?.let { mutableNode(value) }
            }
            nodes.forEachIndexed { index, node ->
                // N * O(1)
                node?.apply {
                    left = nodes.getOrNull(index * 2 + 1)
                    right = nodes.getOrNull(index * 2 + 2)
                }
            }
            // O(1)
            return nodes.firstOrNull()
        }
    }
}

MutableNodeTest.kt

import org.amshove.kluent.`should equal`
import org.junit.jupiter.api.DisplayName
import org.junit.jupiter.params.ParameterizedTest
import org.junit.jupiter.params.provider.Arguments
import org.junit.jupiter.params.provider.MethodSource

internal class MutableNodeTest {

    @DisplayName("MutableNode.fromNonRecursive builds mutableNode graph")
    @MethodSource("parameters")
    @ParameterizedTest
    fun buildsNodeGraphNonRecursively(input: Array<Int?>, expected: MutableNode) {
        val actual = MutableNode.fromNonRecursive(input)
        actual `should equal` expected
    }

    @DisplayName("MutableNode.fromRecursive builds mutableNode graph")
    @MethodSource("parameters")
    @ParameterizedTest
    fun buildsNodeGraphRecursively(input: Array<Int?>, expected: MutableNode) {
        val actual = MutableNode.fromRecursive(input)
        actual `should equal` expected
    }

    @DisplayName("inorderTraversalRecursive yields expected value")
    @MethodSource("inOrderTraversal")
    @ParameterizedTest
    fun recursiveInOrderTraversal(input: Array<Int?>, expected: IntArray) {
        MutableNode.fromRecursive(input)!!.inorderTraversalRecursive() `should equal` expected
    }

    @DisplayName("inorderTraversalNonRecursive yields expected value")
    @MethodSource("inOrderTraversal")
    @ParameterizedTest
    fun nonRecursiveInOrderTraversal(input: Array<Int?>, expected: IntArray) {
        MutableNode.fromNonRecursive(input)!!.inorderTraversalNonRecursive() `should equal` expected
    }

    @DisplayName("preOrderTraversalRecursive yields expected value")
    @MethodSource("preOrderTraversal")
    @ParameterizedTest
    fun recursivePreOrderTraversal(input: Array<Int?>, expected: IntArray) {
        MutableNode.fromRecursive(input)!!.preOrderTraversalRecursive() `should equal` expected
    }

    @DisplayName("preOrderTraversalNonRecursive yields expected value")
    @MethodSource("preOrderTraversal")
    @ParameterizedTest
    fun nonRecursivePreOrderTraversal(input: Array<Int?>, expected: IntArray) {
        MutableNode.fromNonRecursive(input)!!.preOrderTraversalNonRecursive() `should equal` expected
    }

    @DisplayName("postOrderTraversalRecursive yields expected value")
    @MethodSource("postOrderTraversal")
    @ParameterizedTest
    fun recursivePostOrderTraversal(input: Array<Int?>, expected: IntArray) {
        MutableNode.fromRecursive(input)!!.postOrderTraversalRecursive() `should equal` expected
    }

    @DisplayName("postorderTraversalNonRecursive yields expected value")
    @MethodSource("postOrderTraversal")
    @ParameterizedTest
    fun nonRecursivePostOrderTraversal(input: Array<Int?>, expected: IntArray) {
        MutableNode.fromNonRecursive(input)!!.postOrderTraversalNonRecursive() `should equal` expected
    }

    @Suppress("unused")
    companion object {
        @JvmStatic
        fun parameters() = listOf(
            Arguments {
                arrayOf<Any?>(
                    arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, null, null, 11, 12),
                    mutableNode(
                        value = 1,
                        left = mutableNode(
                            value = 2,
                            left = mutableNode(
                                value = 4,
                                left = mutableNode(8),
                                right = mutableNode(9)
                            ),
                            right = mutableNode(
                                value = 5,
                                left = mutableNode(10)
                            )
                        ),
                        right = mutableNode(
                            value = 3,
                            left = mutableNode(
                                value = 6,
                                right = mutableNode(11)
                            ),
                            right = mutableNode(
                                value = 7,
                                left = mutableNode(12)
                            )
                        )
                    )
                )
            }
        )

        @JvmStatic
        fun inOrderTraversal() = listOf(
            Arguments {
                arrayOf<Any?>(
                    arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, null, null, 11, 12),
                    intArrayOf(8, 4, 9, 2, 10, 5, 1, 6, 11, 3, 12, 7)
                )
            }
        )

        @JvmStatic
        fun preOrderTraversal() = listOf(
            Arguments {
                arrayOf<Any?>(
                    arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, null, null, 11, 12),
                    intArrayOf(1, 2, 4, 8, 9, 5, 10, 3, 6, 11, 7, 12)
                )
            }
        )

        @JvmStatic
        fun postOrderTraversal() = listOf(
            Arguments {
                arrayOf<Any?>(
                    arrayOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, null, null, 11, 12),
                    intArrayOf(8, 9, 4, 10, 5, 2, 11, 6, 12, 7, 3, 1)
                )
            }
        )
    }
}