Binary Tree Traversal

class TreeNode<T: Comparable> {
    var value: T
    var left: TreeNode<T>?
    var right: TreeNode<T>?
    
    init(_ value: T) {
        self.value = value
    }
}

class BinaryTree<T: Comparable> {
    private var root: TreeNode<T>?
    
    func insert(_ value: T) {
        root = insertRecursive(root, value)
    }
    
    private func insertRecursive(_ node: TreeNode<T>?, _ value: T) -> TreeNode<T> {
        guard let node = node else {
            return TreeNode(value)
        }
        
        if value < node.value {
            node.left = insertRecursive(node.left, value)
        } else if value > node.value {
            node.right = insertRecursive(node.right, value)
        }
        
        return node
    }
    
    func inOrderTraversal() -> [T] {
        var result: [T] = []
        inOrderRecursive(root, &result)
        return result
    }
    
    private func inOrderRecursive(_ node: TreeNode<T>?, _ result: inout [T]) {
        guard let node = node else { return }
        
        inOrderRecursive(node.left, &result)
        result.append(node.value)
        inOrderRecursive(node.right, &result)
    }
    
    func preOrderTraversal() -> [T] {
        var result: [T] = []
        preOrderRecursive(root, &result)
        return result
    }
    
    private func preOrderRecursive(_ node: TreeNode<T>?, _ result: inout [T]) {
        guard let node = node else { return }
        
        result.append(node.value)
        preOrderRecursive(node.left, &result)
        preOrderRecursive(node.right, &result)
    }
    
    func postOrderTraversal() -> [T] {
        var result: [T] = []
        postOrderRecursive(root, &result)
        return result
    }
    
    private func postOrderRecursive(_ node: TreeNode<T>?, _ result: inout [T]) {
        guard let node = node else { return }
        
        postOrderRecursive(node.left, &result)
        postOrderRecursive(node.right, &result)
        result.append(node.value)
    }
    
    func search(_ value: T) -> Bool {
        return searchRecursive(root, value)
    }
    
    private func searchRecursive(_ node: TreeNode<T>?, _ value: T) -> Bool {
        guard let node = node else { return false }
        
        if value == node.value {
            return true
        } else if value < node.value {
            return searchRecursive(node.left, value)
        } else {
            return searchRecursive(node.right, value)
        }
    }
}

// Example usage
let tree = BinaryTree<Int>()
let values = [50, 30, 70, 20, 40, 60, 80]

for value in values {
    tree.insert(value)
}

print("In-order traversal: \(tree.inOrderTraversal())")
print("Pre-order traversal: \(tree.preOrderTraversal())")
print("Post-order traversal: \(tree.postOrderTraversal())")
print("Search for 40: \(tree.search(40))")
print("Search for 90: \(tree.search(90))")