Day16-Apr-Convert_BST_to_Greater_Tree-Recursive(dfs)

class Solution {

    /**
        Problem Link: https://leetcode.com/problems/trim-a-binary-search-tree/
        Language:
            Swift
        Complexity analysis:
             Space: O(lenght of the recursive stack)
             Time: O(n) - accroding to worst case.
    */

    func convertBST(_ root: TreeNode?) -> TreeNode? {
    /**
        Args:
            root: Custom(TreeNode) data(class) type;
        Return:
            Custom(TreeNode) data(class) type; return the greater tree root node.
    */
        var sum = 0
        //innner method
        func dfs(_ current_node: TreeNode?) -> TreeNode? {
            guard let current_node = current_node else { return nil }

            // visite to right subtree
            dfs(current_node.right)
            sum += current_node.val
            current_node.val = sum

            // visite to left subtree
            dfs(current_node.left)

            return current_node
        }

        return dfs(root)
    }
}