class Tree {

    data class Node(val value: Int) {
        var leftNode: Node? = null
        var rightNode: Node? = null
    }

    var rootNode: Node? = null

    fun insert(value: Int) {
        val newNode = Node(value)
        if (rootNode == null) {
            rootNode = newNode
            return
        }
        var current = rootNode
        while (true) {
            if (value < current!!.value) {
                // add to left.
                if (current.leftNode == null) {
                    current.leftNode = newNode
                    break
                }
                current = current.leftNode
            } else {
                if (current.rightNode == null) {
                    current.rightNode = newNode
                    break
                }
                current = current.rightNode
            }
        }
    }


    fun contains(value: Int): Boolean {
        var current = rootNode
        while (current != null) {
            if (value < current.value) {
                current = current.leftNode
            } else if (value > current.value) {
                current = current.rightNode
            } else {
                return true
            }
        }
        return false
    }

    fun traverseInOrder() {
        traverseInorder(rootNode)
    }

    private fun traverseInorder(root: Node?) {
        // Traverse left recursively
        // Visit the root node.
        // Traverse the right node.
        if (root == null) {
            return
        }
        traverseInorder(root.leftNode)
        println(root.value)
        traverseInorder(root.rightNode)
    }

    fun traversePreOrder() {
        traversePreOrder(rootNode)
    }

    private fun traversePreOrder(root: Node?) {
        // visit the root node.
        // traverse left recursively.
        // traverse right recursively.
        if (root == null) {     // base condition
            return
        }
        println(root.value)
        traversePreOrder(root.leftNode)
        traversePreOrder(root.rightNode)
    }

    fun height(): Int {
        return height(rootNode)
    }


    private fun height(root: Node?): Int {
        // Post order traversal.
        if (isEmpty()) {
            return -1
        }
        if (root?.leftNode == null && root?.rightNode == null) { // base condition..
            return 0
        }
        return 1 + Math.max(height(root.leftNode), height(root.rightNode))
    }

    fun minValue(root: Node?): Int {
        // For binary tree..
        // Time Complexity O(n)
        if (root?.leftNode == null && root?.rightNode == null) {
            return 0;
        }
        val left = minValue(root.leftNode)
        val right = minValue(root.rightNode)
        return Math.min(Math.min(left, right), root.value)
    }

    fun minValueForBST(root: Node?): Int {
        // For Binary Search Tree.
        // Time Complexity O(logn) as we are narrowing down our search
        // by only searching for left nodes.
        if (isEmpty()) {
            throw IllegalStateException()
        }
        var current = rootNode
        var last = current
        while (current != null) {
            last = current
            current = current.leftNode
        }
        return last?.value!!
    }

    fun equal(other: Tree): Boolean {
        return equals(rootNode, other.rootNode)
    }

    private fun equals(firstNode: Node?, secondNode: Node?): Boolean {
        // Preorder traversal.
        if (firstNode == null && secondNode == null) {
            return true
        }
        if (firstNode != null && secondNode != null) {
            return firstNode.value == secondNode.value
                    && equals(firstNode.leftNode, secondNode.leftNode)
                    && equals(firstNode.rightNode, secondNode.rightNode)
        }
        return false
    }

    fun isBinarySearchTree(): Boolean {
        return isBinarySearchTree(rootNode!!, Int.MIN_VALUE, Int.MAX_VALUE)
    }

    private fun isBinarySearchTree(root: Node, min: Int, max: Int): Boolean {
        if (isEmpty()) {
            return true
        }
        if (root.value < min || root.value > max)
            return false
        return isBinarySearchTree(root.leftNode!!, min, root.value - 1)
                && isBinarySearchTree(root.leftNode!!, root.value + 1, max)
    }

    fun printNodesAtDistance(distance: Int) {
        printNodesAtDistance(rootNode, distance)
    }

    private fun printNodesAtDistance(root: Node?, distance: Int) {
        if (root == null) {
            return
        }
        if (distance == 0) {
            println(root.value)
            return
        }
        printNodesAtDistance(root.leftNode, distance - 1)
        printNodesAtDistance(root.rightNode, distance - 1)
    }

    private fun traverseLevelOrder() {
        for (i in 0 until height()) {
            printNodesAtDistance(i)
        }
    }

    private fun isEmpty(): Boolean = rootNode == null

}