O(logn)

op-complexity.kt

import kotlin.random.Random

class Node(var value: Int) {
    var left: Node? = null
    var right: Node? = null
}

class BinaryTree {
    var root: Node? = null

    fun insert(value: Int) {
        root = insertRecursive(root, value)
    }

    private fun insertRecursive(node: Node?, value: Int): Node {
        if (node == null) {
            return Node(value)
        }

        if (value < node.value) {
            node.left = insertRecursive(node.left, value)
        } else if (value > node.value) {
            node.right = insertRecursive(node.right, value)
        }

        return node
    }

    fun find(value: Int): Int {
        return findRecursive(root, value, 0)
    }

    private fun findRecursive(node: Node?, value: Int, count: Int): Int {
        if (node == null) {
            return count
        }

        if (value == node.value) {
            return count
        }

        if (value < node.value) {
            return findRecursive(node.left, value, count + 1)
        } else {
            return findRecursive(node.right, value, count + 1)
        }
    }
}

fun main() {
    for(n in 10..60_000) {
        val tree = BinaryTree()
        repeat (n) {
            val numberToInsert = Random.nextInt(n+1)
            tree.insert(numberToInsert)
        }
        var totSteps = 0
        val numberOfSearches = 1000
        repeat (numberOfSearches) {
            val numberToSearch = Random.nextInt(n+1)
            totSteps += tree.find(numberToSearch)
        }
        val avgSteps = totSteps / numberOfSearches
        println("$n,$avgSteps")
    }
}