// A binary search tree, not a multiway B-tree. Duplicate values are ignored.
// This example is unbalanced; recursive insertion uses Aner's call-depth limit.
class TreeNode {
    public let value: Int64
    public var left: TreeNode?
    public var right: TreeNode?

    fn insert(value: Int64) -> Unit {
        if value < self.value {
            if left == null {
                left = TreeNode(value: value, left: null, right: null)
            } else {
                left.unwrap().insert(value)
            }
        } else if value > self.value {
            if right == null {
                right = TreeNode(value: value, left: null, right: null)
            } else {
                right.unwrap().insert(value)
            }
        }
    }
}

class Tree {
    public var root: TreeNode?

    fn insert(value: Int64) -> Unit {
        if root == null {
            root = TreeNode(value: value, left: null, right: null)
        } else {
            root.unwrap().insert(value)
        }
    }

    fn contains(value: Int64) {
        var cursor = root
        while cursor != null {
            let node = cursor.unwrap()
            if value == node.value {
                return true
            } else if value < node.value {
                cursor = node.left
            } else {
                cursor = node.right
            }
        }
        return false
    }
}

let tree = Tree(root: null)
tree.insert(8)
tree.insert(3)
tree.insert(10)
tree.insert(6)
tree.insert(14)
print("Contains 6")
print(tree.contains(6))
print("Contains 7")
print(tree.contains(7))