public class BstDegenerate {

    static class Node {
        int nilai;
        Node kiri;
        Node kanan;

        Node(int nilai) {
            this.nilai = nilai;
        }
    }

    static long perbandingan;

    public static void main(String[] args) {
        // Pohon A: urutan sisip yang menempatkan nilai tengah lebih dulu.
        Node akarSeimbang = null;
        for (int v : new int[] {4, 2, 6, 1, 3, 5, 7}) {
            akarSeimbang = sisip(akarSeimbang, v);
        }

        // Pohon B: data yang sama namun sudah terurut naik.
        Node akarRantai = null;
        for (int v : new int[] {1, 2, 3, 4, 5, 6, 7}) {
            akarRantai = sisip(akarRantai, v);
        }

        System.out.println("=== Pohon A: sisip 4,2,6,1,3,5,7 ===");
        cetakStruktur(akarSeimbang, 0, "akar");
        System.out.println("Jumlah level: " + jumlahLevel(akarSeimbang));
        perbandingan = 0;
        cari(akarSeimbang, 7);
        System.out.println("cari(7) -> ditemukan, perbandingan: " + perbandingan);

        System.out.println();
        System.out.println("=== Pohon B: sisip 1,2,3,4,5,6,7 (data terurut) ===");
        cetakStruktur(akarRantai, 0, "akar");
        System.out.println("Jumlah level: " + jumlahLevel(akarRantai));
        perbandingan = 0;
        cari(akarRantai, 7);
        System.out.println("cari(7) -> ditemukan, perbandingan: " + perbandingan);
    }

    static Node sisip(Node node, int nilai) {
        if (node == null) {
            return new Node(nilai);
        }
        if (nilai < node.nilai) {
            node.kiri = sisip(node.kiri, nilai);
        } else if (nilai > node.nilai) {
            node.kanan = sisip(node.kanan, nilai);
        }
        return node;
    }

    static boolean cari(Node akar, int nilai) {
        Node sekarang = akar;
        while (sekarang != null) {
            perbandingan++;
            if (nilai == sekarang.nilai) {
                return true;
            }
            if (nilai < sekarang.nilai) {
                sekarang = sekarang.kiri;
            } else {
                sekarang = sekarang.kanan;
            }
        }
        return false;
    }

    static int jumlahLevel(Node node) {
        if (node == null) {
            return 0;
        }
        return 1 + Math.max(jumlahLevel(node.kiri), jumlahLevel(node.kanan));
    }

    static void cetakStruktur(Node node, int indentasi, String posisi) {
        if (node == null) {
            return;
        }
        System.out.println("  ".repeat(indentasi) + posisi + ": " + node.nilai);
        cetakStruktur(node.kiri, indentasi + 1, "kiri");
        cetakStruktur(node.kanan, indentasi + 1, "kanan");
    }
}