Skip to content

Convert BST to Greater Tree

LeetCode

01 · Question

Convert a BST so each node contains the sum of all keys greater than or equal to it.

02 · Solution

Reference solution

1def convertBST(root: Optional[TreeNode]) -> Optional[TreeNode]:
2 total = 0
3 def dfs(node: Optional[TreeNode]) -> None:
4 nonlocal total
5 if not node:
6 return
7 dfs(node.right)
8 total += node.val
9 node.val = total
10 dfs(node.left)
11 dfs(root)
12 return root