import java.util.Arrays;

public class BstManual {

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

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

    private Node akar;

    // Penghitung perbandingan kunci saat pencarian.
    static long perbandingan;

    public static void main(String[] args) {
        int[] data = {50, 30, 70, 20, 40, 60, 80};
        BstManual bst = new BstManual();
        for (int nilai : data) {
            bst.sisip(nilai);
        }

        System.out.println("Sisip berurutan: " + Arrays.toString(data));
        System.out.println();
        System.out.println("Struktur pohon:");
        cetakStruktur(bst.akar, 0, "akar");

        System.out.println();
        System.out.println("inorder   : " + bacaTraversal(bst.akar, "inorder"));
        System.out.println("preorder  : " + bacaTraversal(bst.akar, "preorder"));
        System.out.println("postorder : " + bacaTraversal(bst.akar, "postorder"));

        System.out.println();
        perbandingan = 0;
        boolean ketemu = bst.cari(40);
        System.out.println("cari(40) -> " + ketemu + ", perbandingan: " + perbandingan);

        perbandingan = 0;
        ketemu = bst.cari(65);
        System.out.println("cari(65) -> " + ketemu + ", perbandingan: " + perbandingan);
    }

    void sisip(int nilai) {
        akar = sisipRekursif(akar, nilai);
    }

    private static Node sisipRekursif(Node node, int nilai) {
        if (node == null) {
            return new Node(nilai);        // titik kosong: tempat node baru
        }
        if (nilai < node.nilai) {
            node.kiri = sisipRekursif(node.kiri, nilai);
        } else if (nilai > node.nilai) {
            node.kanan = sisipRekursif(node.kanan, nilai);
        }
        // nilai sama: diabaikan, BST tidak menyimpan duplikat
        return node;
    }

    boolean cari(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 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");
    }

    static String bacaTraversal(Node node, String jenis) {
        StringBuilder sb = new StringBuilder();
        traversal(node, jenis, sb);
        return sb.toString();
    }

    private static void traversal(Node node, String jenis, StringBuilder sb) {
        if (node == null) {
            return;
        }
        if (jenis.equals("preorder")) {
            sb.append(node.nilai).append(' ');
        }
        traversal(node.kiri, jenis, sb);
        if (jenis.equals("inorder")) {
            sb.append(node.nilai).append(' ');
        }
        traversal(node.kanan, jenis, sb);
        if (jenis.equals("postorder")) {
            sb.append(node.nilai).append(' ');
        }
    }
}