Watch 10 video solutions for Convert BST to Greater Tree, a medium level problem involving Tree, Depth-First Search, Binary Search Tree. This walkthrough by NeetCode has 25,414 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given the root of a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus the sum of all keys greater than the original key in BST.
As a reminder, a binary search tree is a tree that satisfies these constraints:
Example 1:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Example 2:
Input: root = [0,null,1] Output: [1,null,1]
Constraints:
[0, 104].-104 <= Node.val <= 104root is guaranteed to be a valid binary search tree.
Note: This question is the same as 1038: https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/