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

• 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``````

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