import UIKit

class TreeNode<T: Comparable> {
    var parent: TreeNode?
    var value: T
    var left: TreeNode?
    var right: TreeNode?
    
    var isLeaf: Bool {
        return left == nil && right == nil
    }
    
    var isRoot: Bool {
        return parent == nil
    }
    
    init(_ value: T) {
        self.value = value
    }
}

class BinarySearchTree<T: Comparable> {
    var root: TreeNode<T>?
    
    func insert(_ value: T) {
        root = insert(from: root, value: value)
    }
    
    private func insert(from node: TreeNode<T>?, value: T, parent: TreeNode<T>? = nil) -> TreeNode<T> {
        guard let node else {
            let node = TreeNode(value)
            node.parent = parent
            return node
        }
        
        if value < node.value {
            node.left = insert(from: node.left, value: value, parent: node)
        } else {
            node.right = insert(from: node.right, value: value, parent: node)
        }
        return node
    }
    
    func search(_ value: T) -> TreeNode<T>? {
        return search(from: root, value: value)
    }
    
    private func search(from node: TreeNode<T>?, value: T) -> TreeNode<T>? {
        guard let node = node else { return nil }
        
        if value == node.value {
            return node
        } else if value < node.value {
            return search(from: node.left, value: value)
        } else {
            return search(from: node.right, value: value)
        }
    }
    
    func printInOrder() {
        inOrderTraversal(node: root)
    }
    
    private func inOrderTraversal(node: TreeNode<T>?) {
        guard let node = node else { return }
        
        inOrderTraversal(node: node.left)
        print(node.value)
        inOrderTraversal(node: node.right)
    }
}

// Example usage:
let bst = BinarySearchTree<Int>()
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)

bst.printInOrder()  // Output should be in order: 1 3 5 7 9

let node = bst.search(9)
print(node?.isRoot ?? false)