fun main(args: Array<String>) {
    val binaryTree = BinaryTree<Int>()
    repeat(readLine()?.toInt() ?: 0) {
        val input = readLine()?.split(" ".toRegex()) ?: return@repeat
        when (input[0]) {
            "insert" -> binaryTree.insert(input[1].toInt())
            "delete" -> binaryTree.delete(input[1].toInt())
            "print" -> binaryTree.printTree()
            "find" -> println(
                if (binaryTree.exists(input[1].toInt())) {
                    "yes"
                } else {
                    "no"
                }
            )
        }
    }
}

class BinaryTree<T: Comparable<T>> {
    private var root: Node? = null

    fun insert(key: T) {
        val newNode = Node(key)
        var x = root
        var y = x?.parent
        while (x != null) {
            y = x
            x = if (key < x.key) {
                x.leftChild
            } else {
                x.rightChild
            }
        }
        newNode.parent = y
        when {
            y == null -> root = newNode
            key < y.key -> y.leftChild = newNode
            else -> y.rightChild = newNode
        }
    }

    fun find(key: T): Node? {
        var node = this.root
        while (node != null) {
            if (key == node.key) {
                return node
            } else if (key < node.key) {
                node = node.leftChild
            } else {
                node = node.rightChild
            }
        }
        return null
    }

    fun exists(key: T): Boolean {
        var node = this.root
        while (node != null) {
            if (key == node.key) {
                return true
            } else if (key < node.key) {
                node = node.leftChild
            } else {
                node = node.rightChild
            }
        }
        return false
    }

    fun delete(key: T) {
        val node = find(key)
        val deleteNode = if (node?.leftChild == null || node.rightChild == null) {
            node
        } else {
            getSuccessor(node)
        }

        val child = if (deleteNode?.leftChild != null) {
            deleteNode.leftChild
        } else {
            deleteNode?.rightChild
        }

        if (child != null) {
            child.parent = deleteNode?.parent
        }

        if (deleteNode?.parent == null) {
            root = child
        } else if (deleteNode == deleteNode.parent?.leftChild) {
            deleteNode.parent?.leftChild = child
        } else {
            deleteNode.parent?.rightChild = child
        }

        if (deleteNode?.key != null && deleteNode !== node) {
            node?.key = deleteNode.key
        }
    }

    fun getSuccessor(node: Node): Node? {
        if (node.rightChild != null) {
            return getMinimum(node.rightChild!!)
        }
        var x = node
        var y = x.parent
        while (y != null && x === y.rightChild) {
            x = y
            y = y.parent
        }
        return y
    }

    fun getMinimum(rootNode: Node): Node? {
        var node: Node? = rootNode
        while (node?.leftChild != null) {
            node = node.leftChild
        }
        return node
    }

    fun printTree() {
        println(inorderTreeWalk())
        println(preorderTreeWalk())
    }

    private fun inorderTreeWalk(): String {
        val root = this.root ?: return ""
        return inorderTreeWalk(root)
    }

    private fun inorderTreeWalk(node: Node): String {
        val resultBuilder = StringBuilder()
        if (node.leftChild != null) {
            resultBuilder.append(inorderTreeWalk(node.leftChild!!))
        }
        resultBuilder.append(" ")
        resultBuilder.append(node.key)
        if (node.rightChild != null) {
            resultBuilder.append(inorderTreeWalk(node.rightChild!!))
        }
        return resultBuilder.toString()
    }

    private fun preorderTreeWalk(): String {
        val root = this.root ?: return ""
        return preorderTreeWalk(root)
    }

    private fun preorderTreeWalk(node: Node): String {
        val resultBuilder = StringBuilder()
        resultBuilder.append(" ")
        resultBuilder.append(node.key)
        if (node.leftChild != null) {
            resultBuilder.append(preorderTreeWalk(node.leftChild!!))
        }
        if (node.rightChild != null) {
            resultBuilder.append(preorderTreeWalk(node.rightChild!!))
        }
        return resultBuilder.toString()
    }

    inner class Node(var key: T) {
        var parent: Node? = null
        var leftChild: Node? = null
        var rightChild: Node? = null
    }
}


Measured memory_bytes: 572572