BinarySearchTree.kt

class BinarySearchTree<T : Comparable<T>>() {
    private var root: BinaryNode<T>? = null

    constructor(element: T) : this() {
        root = BinaryNode(element)
    }

    fun getRoot() = root

    fun insert(element: T) : Boolean {
        val tmp = BinaryNode(element)
        if (root == null) {
            root = tmp
            return true
        }

        var current = root as BinaryNode
        while (true) {
            if (element < current.value) {
                if (current.left == null) { current.left = tmp; break }
                current = current.left as BinaryNode
            } else {
                if (current.right == null) { current.right = tmp; break }
                current = current.right as BinaryNode
            }
        }
        return true
    }

    fun contains(element: T) : Boolean {
        var current = root as BinaryNode
        while (true) {
            when {
                element < current.value -> current = current.left as? BinaryNode ?: return false
                element == current.value -> return true
                element > current.value -> current = current.right as? BinaryNode ?: return false
            }
        }
    }

    fun preOrder(n: BinaryNode<T>) {
        print(n.value)
        if (n.left != null) preOrder(n.left as BinaryNode)
        if (n.right != null) preOrder(n.right as BinaryNode)
    }

    fun midOrder(n: BinaryNode<T>) {
        if (n.left != null) midOrder(n.left as BinaryNode)
        print(n.value)
        if (n.right != null) midOrder(n.right as BinaryNode)
    }

    fun backOrder(n: BinaryNode<T>) {
        if (n.left != null) backOrder(n.left as BinaryNode)
        if (n.right != null) backOrder(n.right as BinaryNode)
        print(n.value)
    }

    fun midOrderNonRec() {
        val stack = Stack<BinNodeWState<T>>(64)
        var current: BinNodeWState<T>

        stack.push(root?.toBinNodeWState() ?: return)
        while (!stack.isEmpty) {
            current = stack.top as BinNodeWState<T>
            when (current.state) {
                0 -> {
                    if (current.left != null)
                        stack.push(current.left as BinNodeWState<T>)
                    current.state = 1
                }
                1 -> {
                    print(current.value)
                    current.state = 2
                }
                2 -> {
                    if (current.right != null)
                        stack.push(current.right as BinNodeWState<T>)
                    current.state = 3
                }
                3 -> {
                    stack.pop()
                    current.state = 0
                }
            }
        }
    }

    fun preOrderNonRec() {
        val stack = Stack<BinNodeWState<T>>(64)
        var current: BinNodeWState<T>

        stack.push(root?.toBinNodeWState() ?: return)
        while (!stack.isEmpty) {
            current = stack.top as BinNodeWState<T>
            when (current.state) {
                0 -> {
                    print(current.value)
                    current.state = 1
                }
                1 -> {
                    if (current.left != null)
                        stack.push(current.left as BinNodeWState<T>)
                    current.state = 2
                }
                2 -> {
                    if (current.right != null)
                        stack.push(current.right as BinNodeWState<T>)
                    current.state = 3
                }
                3 -> {
                    stack.pop()
                    current.state = 0
                }
            }
        }
    }

    fun layerIterate() {
        val stack = Stack<BinaryNode<T>>(64)
        var layerNow = 0

        stack.push(root ?: return)
        while (!stack.isEmpty) {
            val tmp = Stack<BinaryNode<T>>(1 shl layerNow)
            while (!stack.isEmpty) {
                tmp.push(stack.pop())
                print(tmp.top?.value)
            }
            while (!tmp.isEmpty) {
                val tmpNode = tmp.pop()
                if (tmpNode.right != null) stack.push(tmpNode.right as BinaryNode<T>)
                if (tmpNode.left != null) stack.push(tmpNode.left as BinaryNode<T>)
            }
            layerNow++
        }
    }

    internal class BinNodeWState<T: Comparable<T>>(val value: T) {
        var state = 0
        var left: BinNodeWState<T>? = null
        var right: BinNodeWState<T>? = null
    }


    internal fun BinaryNode<T>.toBinNodeWState() : BinNodeWState<T> {
        val root = BinNodeWState(this.value)
        root.left = this.left?.toBinNodeWState()
        root.right = this.right?.toBinNodeWState()
        return root
    }
}