Python solution iterative & recursive O(n) time and O(1) space with explaination


  • 1
    Z

    Here is how I reached to this solution.

    1. When I first look at this question, I know I can solve it by in order tree traversal, since in order traversal of BST will give us a sorted list of nodes in ascending order.

    2. This solution has an obvious issue, after we get a list of sorted nodes, we still need to calculate the sum of all values after each nodes, then I was thinking of using some dynamic programming techniques to do backward range sum.

    3. Wait a second, since we will need to do range sum from the back, why not just do it while traverse the tree, then the solution is obvious, just simply traverse the tree in reverse order and keep adding up the values, we can use a variable to store the current sum of all nodes start from the back.

    Here are some python version of this algorithm.

    Iterative

    class Solution(object):
        def convertBST(self, root):
            tmp, stack, total = root, [], 0
            while root or stack:
                if root:
                    stack.append(root)
                    root = root.right
                else:
                    root = stack.pop()
                    total += root.val
                    root.val = total
                    root = root.left
            return tmp
    

    Recursive

    class Solution(object):
        def convertBST(self, root):
            self.sum = 0
            def helper(root):
                if root.right:
                    helper(root.right)
                self.sum += root.val
                root.val = self.sum
                if root.left:
                    helper(root.left)
            if root:
                helper(root)
            return root
    

    UPDATE
    Added morris tree traversal to reduce the space complexity to O(1)

    class Solution(object):
        def convertBST(self, root):
            tmp, total = root, 0
            while root:
                if not root.right:
                    total += root.val
                    root.val = total
                    root = root.left
                else:
                    pred = root.right
                    while pred.left and pred.left is not root:
                        pred = pred.left
                    if pred.left is root:
                        pred.left = None
                        total += root.val
                        root.val = total
                        root = root.left
                    else:
                        pred.left = root
                        root = root.right
            return tmp

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.