Determine if a given binary search tree is valid.

Valid Binary Search Tree.swift

final class Node {
    let left: Node?
    let right: Node?
    let value: Int
    
    init(left: Node? = nil, right: Node? = nil, value: Int) {
        self.left = left
        self.right = right
        self.value = value
    }
}

struct Stack<T> {
    private var storage = [T]()
    
    mutating func push(_ item: T) {
        storage.append(item)
    }
    mutating func pop() -> T? {
        storage.removeLast()
    }
    
    var height: Int { storage.count }
}

final class TreeProcessor {
    // MARK: - Iteritive Solution
    func isValidBinarySearchTreeIteritive(_ tree: Node) -> Bool {
        var stack = Stack<Node>()
        stack.push(tree)
        
        var rangeForNode = [Int: Range<Int>]()
        
        repeat {
            guard let node = stack.pop() else { return true }
            
            let range = rangeForNode[node.value] ?? 0..<Int.max
            
            guard range.contains(node.value),
                let start = range.first,
                let end = range.last  else { return false }
            
            print("valid node: \(node.value)")
            
            if let left = node.left {
                rangeForNode[left.value] = start..<node.value
                stack.push(left)
            }
            
            if let right = node.right {
                rangeForNode[right.value] = node.value..<end
                stack.push(right)
            }
        } while stack.height != 0
        return true
    }
    
    // MARK: - Recursive Solution
    func isValidBinarySearchTree(_ tree: Node) -> Bool {
        return isValid(node: tree)
    }

    func isValid(node: Node?, in range: Range<Int> = 0..<Int.max) -> Bool {
        guard let node = node else { return true }
        
        guard
            range.contains(node.value),
            let start = range.first,
            let end = range.last,
            isValid(node: node.right, in: node.value..<end),
            isValid(node: node.left, in: start..<node.value)
            else { return false }
        print("valid node: \(node.value)")
        return true
    }
}

let tree = Node(left: .init(value: 1),
                right: .init(left: .init(value: 6),
                             right: .init(value: 8),
                             value: 7),
                value: 5)

TreeProcessor().isValidBinarySearchTreeIteritive(tree) // => true

/*
    valid node: 5
    valid node: 7
    valid node: 8
    valid node: 6
    valid node: 1
*/

TreeProcessor().isValidBinarySearchTree(tree) // => true

/*
    valid node: 8
    valid node: 6
    valid node: 7
    valid node: 1
    valid node: 5
*/