depth-first-search-number.kt

fun main(args: Array<String>) {
    var tos = Node(5) //Membuat Node 5 sebagai parent tree
    tos.left = Node(4) //Menambahkan Node 4 sebagai left child dari parent
    tos.right = Node(6) //Menambahkan Node 6 sebagai right child dari parent
    
    var tempLeft = Node(tos.left) //Menyimpan left node dari Parent ke variabel penampung
    tempLeft.left = Node(2) //Menambahkan Node 2 sebagai left node dari node 4
    tempLeft.right = Node(3, Node(8), null) //Menambahkan Node 3 sebagai right node dari node 4, lalu ditambahkan node 8 sebagai left node dari node 3
    tos.left = Node(tempLeft) //Mengembalikan node yang ada pada variabel penampung ke left node parent
    
    var tempRight = Node(tos.right) //Menyimpan right node dari Parent ke variabel penampung
    tempRight.left = Node(1, null, Node(9)) //Menambahkan Node 1 pada Left Node 6. Lalu menambahkan Node 9 sebagai Right Node dari Node 1
    tempRight.right = Node(7, null, Node(0)) //Menambahkan Node 7 pada right Node dari Node 6. Lalu menambahkan Node 0 sebagai Right Node dari Node 7.
    tos.right = Node(tempRight) //Mengembalikan data Node yang ada di variabel penampung kembali ke right node dari parent
    
    printTree(tos, 9) //Mencari Node bernilai 9 dari tree bernama tos
}

class Node {
    var value: Int? = null
    var left: Node? = null
    var right: Node? = null
    constructor(pValue: Int?, pLeft: Node?, pRight: Node?){
        value = pValue
        left = pLeft
        right = pRight
    }
    constructor(pValue: Int?){
        value = pValue
        left = null
        right = null
    }
    constructor(pNode: Node?){
        if(pNode != null){
            value = pNode.value
            left = pNode.left
            right = pNode.right
        }
    }
}

fun tambahNode(nodeBaru: Node, nodeParent: Node?): Node{
    if(nodeParent!=null){
        if(nodeParent.left == null) nodeParent.left = nodeBaru else nodeParent.right = nodeBaru
        return nodeParent
    }
    return Node(nodeBaru.value)
}

fun printNode(node: Node){
    var value = node.value
    var left = node.left
    var right = node.right
    println("Node dengan nilai $value memiliki node $left di kiri dan node $right di kanan")
}

fun printTree(node: Node?, key: Int){
    var (result, path) = printTreeAdvance(node, key, "Node yang dilewati: ", "")
    println(result)
    println("Rute tercepat menggunakan DFS: $path")
}

fun printTreeAdvance(node: Node?, key: Int, pHasil: String, pPath: String): Pair<String,String>{
    var hasil = pHasil
    var path = pPath
    if(node != null){
        if(node.value != null){
            var value = node.value
            hasil = "$hasil $value"
            if(key.toString() == hasil[hasil.length - 1].toString()) path = "$value $path"
            if(node.left != null && key.toString() != hasil[hasil.length - 1].toString()){
                var (hasilBaru, pathBaru) = printTreeAdvance(node.left, key, hasil, path)
                hasil = hasilBaru
                path = pathBaru
                if(key.toString() == hasil[hasil.length - 1].toString()) path = "$value $path"
            } 
            if(node.right != null && key.toString() != hasil[hasil.length - 1].toString()){
                var (hasilBaru, pathBaru) = printTreeAdvance(node.right, key, hasil, path)
                hasil = hasilBaru
                path = pathBaru
                if(key.toString() == hasil[hasil.length - 1].toString()) path = "$value $path"
            }
        }
    } 
    return Pair(hasil, path)
}