/**
 * Beispiel aus
 *
 * - Algorithmen und Datenstrukturen für Dummies
 *   - von Andreas Gogol-Döring und Thomas Letschert
 *   - Verlag Wiley-VCH; Oktober 2019
 *  - Kapitel 5, Bäume: Immer einer über den anderen
 *
 * @author A. Gogol-Döring, Th. Letschert
 */

import Foundation

struct AuD_05_03_InorderTraversal {

    enum BinTree<A> : CustomStringConvertible {
        case Empty
        indirect case Node(value:  A,
                           left:   BinTree,
                           right:  BinTree
        )
        var description : String {
            switch self {
            case .Empty: return "."
            case .Node(let v, let l, let r): return "[\(v), \(l.description), \(r.description) ]"
            }
        }
    }

    static func inorder<A>(tree: BinTree<A>) -> [A] {
        switch tree {
        case .Empty :
            return []
        case .Node(let v, let l, let r) :
            return inorder(tree: l) + ([v] + inorder(tree: r))
        }
    }

    static func run() {
        let tree: BinTree<Int> =
                .Node(value: 1,
                        left: .Node(value: 2,
                                left: .Empty, right: .Empty),
                        right: .Node(value: 3,
                                left: .Node(value: 4, left: .Empty, right: .Empty),
                                right: .Node(value: 5,
                                        left: .Node(value: 6, left: .Empty, right: .Node(value: 7, left: .Empty, right: .Empty)),
                                        right: .Node(value: 8, left: .Empty, right: .Node(value: 9, left: .Empty, right: .Empty)))
                        )
                )

        print(inorder(tree: tree))
    }

}