Условие

В бинарное дерево поиска добавляются элементы. Выведите глубину для каждого добавленного элемента в том порядке, как они добавлялись. Если элемент уже есть в дереве, то ничего добавлять и выводить не нужно. Глубиной называется расстояние от корня дерева до элемента включительно.

Примеры

Ввод: 7 3 2 1 9 5 4 6 8 0 Вывод: 1 2 3 4 2 3 4 4 3

Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter

// Класс узла бинарного дерева поиска (BST)
class Node(val value: Int) {
    var left: Node? = null
    var right: Node? = null
}

// Класс бинарного дерева поиска (BST)
class BST {
    var root: Node? = null // Корневой узел дерева

    // Метод вставки нового элемента в дерево, возвращает глубину вставленного узла
    fun insert(value: Int): Int {
        if (root == null) { // Если дерево пустое, создаем корневой узел
            root = Node(value)
            return 1
        }
        return insertRec(root, value, 1) // Рекурсивная вставка с начальной глубиной 1
    }

    // Рекурсивный метод вставки значения в дерево с учетом глубины
    private fun insertRec(node: Node?, value: Int, depth: Int): Int {
        if (node == null) return depth // Возвращаем глубину, если узел найден пустым
        return when {
            value < node.value -> { // Вставляем в левое поддерево
                if (node.left == null) {
                    node.left = Node(value)
                    depth + 1 // Возвращаем глубину нового узла
                } else {
                    insertRec(node.left, value, depth + 1) // Продолжаем поиск
                }
            }
            value > node.value -> { // Вставляем в правое поддерево
                if (node.right == null) {
                    node.right = Node(value)
                    depth + 1 // Возвращаем глубину нового узла
                } else {
                    insertRec(node.right, value, depth + 1) // Продолжаем поиск
                }
            }
            else -> -1 // Число уже есть в дереве, не вставляем
        }
    }
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val bst = BST() // Создаем экземпляр бинарного дерева поиска
    val parts = reader.readLine().split(" ").map { it.toInt() } // Читаем входные данные
    val depths = mutableListOf<Int>() // Список для хранения глубин вставки

    // Вставляем числа в дерево, прерываемся при встрече 0
    for (num in parts) {
        if (num == 0) break
        val depth = bst.insert(num)
        if (depth != -1) depths.add(depth) // Добавляем глубину, если число вставлено
    }

    writer.write(depths.joinToString(" ") + "\\n") // Выводим глубины вставленных элементов

    reader.close()
    writer.flush()
    writer.close()
}