class Node {
    var left, right: Node?
    var data: Int
    init(data: Int, left: Node? = nil, right: Node? = nil) {
        self.data = data
        self.left = left
        self.right = right
    }
    
    func insert(value: Int) {
        // if value is less or equal to "data", insert on left side,
        // otherwise, insert on right.
        //
        if value <= data { // insert on left
            if left == nil {
                left = Node(data: value)
            } else {
                left?.insert(value: value)
            }
        }
        else { // insert on right
            if right == nil {
                right = Node(data: value)
            } else {
                right?.insert(value: value)
            }
        }
    }
    
    func contains(_ value: Int) -> Bool {
        if value == data {
            return true
        }
        else if value < data {
            if left == nil { return false }
            return left!.contains(value)
        }
        else {
            if right == nil { return false }
            return right!.contains(value)
        }
    }
    
    func printInOrder() {
        left?.printInOrder()
        print(data)
        right?.printInOrder()
    }
    
    func printPreOrder() {
        print(data)
        left?.printInOrder()
        right?.printInOrder()
    }
    
    func printPostOrder() {
        left?.printInOrder()
        right?.printInOrder()
        print(data)
    }
}