verifyBST.swift

// The key to this problem is In-Order traversal and remember the value of last visited node
func verifyBST(node: Node?, lastValue: inout Int?) -> Bool {
    guard let node = node else { return true }

    // since we're doing in-order traversal,
    //  the lastValue from previous traversal path must be <= current value
    if let prevVal = lastValue, prevVal > node.data { return false }

    // visit left
    if !verifyBST(node: node.left, lastValue: &lastValue) { return false }

    // comapre and visit self
    if let leftValue = lastValue, leftValue > node.data { return false }
    lastValue = node.data

    // visit right
    if !verifyBST(node: node.right, lastValue: &lastValue) { return false }

    return true
}

print("\nVerify BST")
// a good BST
root = Node(data: 20)
root.left = Node(data: 10)
root.left?.left = Node(data: 5)
root.left?.right = Node(data: 15)
root.right = Node(data: 30)
root.right?.left = Node(data: 25)
var lastValue: Int? = nil
print("is true BST: \(verifyBST(node: root, lastValue: &lastValue))")

print("\n")
// the following tree's left->right (22) is larger than the root
root = Node(data: 20)
root.left = Node(data: 10)
root.left?.left = Node(data: 5)
root.left?.right = Node(data: 22)
root.right = Node(data: 30)
root.right?.left = Node(data: 26)
print("is true BST: \(verifyBST(node: root, lastValue: &lastValue))")

print("\n")
// the following tree's right->left (18) is smaller than the root
root = Node(data: 20)
root.left = Node(data: 10)
root.left?.left = Node(data: 5)
root.left?.right = Node(data: 15)
root.right = Node(data: 30)
root.right?.left = Node(data: 18)
root.right?.right = Node(data: 35)
print("is true BST: \(verifyBST(node: root, lastValue: &lastValue))")