Tree dan Binary Search Tree

// Demo Tree dan Binary Search Tree: terminologi, operasi insert/search, traversal.

class TreeNode<T : Comparable<T>>(val data: T) {
    var left: TreeNode<T>? = null
    var right: TreeNode<T>? = null
}

class BinarySearchTree<T : Comparable<T>> {
    private var root: TreeNode<T>? = null
    private var size = 0

    fun size(): Int = size

    fun isEmpty(): Boolean = root == null

    // Insert: O(log n) rata-rata, O(n) worst case
    fun insert(data: T) {
        root = insertRec(root, data)
        size++
    }

    private fun insertRec(node: TreeNode<T>?, data: T): TreeNode<T> {
        if (node == null) return TreeNode(data)
        when {
            data < node.data -> node.left = insertRec(node.left, data)
            data > node.data -> node.right = insertRec(node.right, data)
            else -> {
                size--  // data sudah ada, tidak insert duplicate
                return node
            }
        }
        return node
    }

    // Search: O(log n) rata-rata, O(n) worst case
    fun search(data: T): Boolean {
        var curr = root
        while (curr != null) {
            when {
                data == curr.data -> return true
                data < curr.data -> curr = curr.left
                else -> curr = curr.right
            }
        }
        return false
    }

    // In-order traversal: kiri -> root -> kanan (menghasilkan sorted)
    fun inOrder(): List<T> {
        val result = mutableListOf<T>()
        inOrderRec(root, result)
        return result
    }

    private fun inOrderRec(node: TreeNode<T>?, result: MutableList<T>) {
        if (node != null) {
            inOrderRec(node.left, result)
            result.add(node.data)
            inOrderRec(node.right, result)
        }
    }

    // Pre-order: root -> kiri -> kanan
    fun preOrder(): List<T> {
        val result = mutableListOf<T>()
        preOrderRec(root, result)
        return result
    }

    private fun preOrderRec(node: TreeNode<T>?, result: MutableList<T>) {
        if (node != null) {
            result.add(node.data)
            preOrderRec(node.left, result)
            preOrderRec(node.right, result)
        }
    }

    // Post-order: kiri -> kanan -> root
    fun postOrder(): List<T> {
        val result = mutableListOf<T>()
        postOrderRec(root, result)
        return result
    }

    private fun postOrderRec(node: TreeNode<T>?, result: MutableList<T>) {
        if (node != null) {
            postOrderRec(node.left, result)
            postOrderRec(node.right, result)
            result.add(node.data)
        }
    }

    // Height: panjang path terpanjang dari root ke leaf
    fun height(): Int = heightRec(root)

    private fun heightRec(node: TreeNode<T>?): Int {
        if (node == null) return 0
        return 1 + maxOf(heightRec(node.left), heightRec(node.right))
    }

    // Min dan Max
    fun min(): T? {
        var curr: TreeNode<T>? = root ?: return null
        while (curr?.left != null) curr = curr.left
        return curr?.data
    }

    fun max(): T? {
        var curr: TreeNode<T>? = root ?: return null
        while (curr?.right != null) curr = curr.right
        return curr?.data
    }
}

fun main() {
    println("=== Demo Tree dan Binary Search Tree ===")

    val bst = BinarySearchTree<Int>()
    val data = listOf(50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45)
    data.forEach { bst.insert(it) }

    println("--- BST setelah insert ${data.sorted()} ---")
    println("Size: ${bst.size()}")
    println("Height: ${bst.height()}")
    println("Min: ${bst.min()}")
    println("Max: ${bst.max()}")

    println()
    println("--- Traversal ---")
    println("In-order (sorted): ${bst.inOrder()}")
    println("Pre-order: ${bst.preOrder()}")
    println("Post-order: ${bst.postOrder()}")

    println()
    println("--- Search ---")
    listOf(40, 45, 100, 10, 80).forEach {
        println("Search $it: ${if (bst.search(it)) "ditemukan" else "tidak ada"}")
    }

    println()
    println("--- Visualisasi struktur ---")
    //                 50
    //              /      \
    //            30        70
    //           /  \      /  \
    //         20    40   60   80
    //        / \   / \
    //      10  25 35 45
    println("Root: 50")
    println("Left subtree (root 30): left=20 (10, 25), right=40 (35, 45)")
    println("Right subtree (root 70): left=60, right=80")

    println()
    println("--- BST untuk String ---")
    val bstStr = BinarySearchTree<String>()
    listOf("Budi", "Andi", "Siti", "Dewi", "Rina", "Andi").forEach { bstStr.insert(it) }
    println("In-order (sorted alphabetically): ${bstStr.inOrder()}")
    println("Search 'Siti': ${bstStr.search("Siti")}")
    println("Search 'Zaki': ${bstStr.search("Zaki")}")
}

=== Demo Tree dan Binary Search Tree ===
--- BST setelah insert [10, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80] ---
Size: 11
Height: 4
Min: 10
Max: 80

--- Traversal ---
In-order (sorted): [10, 20, 25, 30, 35, 40, 45, 50, 60, 70, 80]
Pre-order: [50, 30, 20, 10, 25, 40, 35, 45, 70, 60, 80]
Post-order: [10, 25, 20, 35, 45, 40, 30, 60, 80, 70, 50]

--- Search ---
Search 40: ditemukan
Search 45: ditemukan
Search 100: tidak ada
Search 10: ditemukan
Search 80: ditemukan

--- Visualisasi struktur ---
Root: 50
Left subtree (root 30): left=20 (10, 25), right=40 (35, 45)
Right subtree (root 70): left=60, right=80

--- BST untuk String ---
In-order (sorted alphabetically): [Andi, Budi, Dewi, Rina, Siti]
Search 'Siti': true
Search 'Zaki': false