Day18-Apr-Kth Smallest_in_a_BST

class Solution {
    /// Languages:
    /// - Swift
    /// Complexity:
    /// - Time: (n)
    /// - Space: (Recursive stack length)

    func kthSmallest(_ root: TreeNode?, _ k: Int) -> Int {
        /// find the kth smallest value.
        /// - parameters:
        ///   - root: TreeNode
        /// - returns: the kth smallest value

        guard let root = root else { return -1 }

        var k = k
        var ans: Int?

        // inner function
        func inorderTraversal(_ root: TreeNode) {
            if let left = root.left {
                inorderTraversal(left)
            }

            k -= 1
            if k == 0 {
                ans = root.val
                return
            }

            if let right = root.right {
                inorderTraversal(right)
            }
        }

        inorderTraversal(root)

        return ans ?? 0
    }
}