# Convert BST to Greater Tree

Tree

## # Definition for a Binary Tree Node

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

1
2
3
4
5

## # Solution

### # Recursion

For a BST, root.left.val < root.val < root.right.val, so update in the order of right, root, and then left.

Complexity

time: $O(n)$
space: $O(n)$

def convertBST(self, root: TreeNode) -> TreeNode:
self.total = 0
self.traverse(root)
return root

def traverse(self, root: TreeNode):
if not root:
return

# traverse the right node recursively
if root.right:
self.traverse(root.right)

# update total and root.val
self.total += root.val
root.val = self.total

# traverse the left node
self.traverse(root.left)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

### # Iteration w/ a Stack

Complexity

time: $O(n)$
space: $O(n)$

def convertBST(self, root: TreeNode) -> TreeNode:
stack = []
node = root
total = 0
while stack or node:
while node:
# add the node and right subtree to stack
stack.append(node)
node = node.right

# update node vals
node = stack.pop()
total += node.val
node.val = total
# at last, traverse the left node
node = node.left

return root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18