#538

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Convert BST to Greater Tree

Convert a BST into a Greater Tree by updating each node’s value with the sum of all greater values in the tree.

tree depth first search binary search tree binary tree

Problem Statement

Given the root of a Binary Search Tree (BST), the task is to convert it into a Greater Tree. In the resulting tree, every node’s value will be updated to the sum of the original value plus the values of all nodes greater than it in the BST.

The conversion must be done efficiently, respecting the properties of the BST. A traversal method such as depth-first search (DFS) can help keep track of the cumulative sum of nodes processed so far while ensuring the tree structure is maintained.

Examples

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 details omitted.

Example 2

Input: root = [0,null,1]

Output: [1,null,1]

Example details omitted.

Constraints

The number of nodes in the tree is in the range [0, 104].
-104 <= Node.val <= 104
All the values in the tree are unique.
root is guaranteed to be a valid binary search tree.

Solution Approach

Depth-First Search (DFS) Traversal

A reverse in-order traversal (right to left) is used to ensure the sum of greater values is accumulated while visiting each node. This allows efficient updates of node values.

State Tracking for Accumulation

During the DFS traversal, maintain a variable that tracks the running total of values greater than the current node. Update each node’s value by adding this running total before moving to the left child.

In-place Tree Modification

The transformation happens in-place, meaning the tree structure is altered without the need for additional memory for a new tree. This ensures the solution is both space and time-efficient.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(N) where N is the number of nodes in the tree, as every node is visited once. The space complexity depends on the depth of recursion, O(H) where H is the height of the tree, which in the worst case is O(N).

What Interviewers Usually Probe

Check if the candidate handles tree traversal correctly and efficiently.
Assess how well the candidate manages state tracking during DFS traversal.
Evaluate whether the candidate ensures the space complexity remains minimal by avoiding extra data structures.

Common Pitfalls or Variants

Common pitfalls

Failing to handle the reverse in-order traversal properly, which leads to incorrect accumulation of greater values.
Not updating the current node’s value before moving to its left child.
Using unnecessary extra space or auxiliary data structures that increase space complexity unnecessarily.

Follow-up variants

Implementing an iterative solution instead of recursion using a stack to simulate the DFS traversal.
Optimizing the solution to handle very large trees with limited memory by using an iterative approach.
Modifying the tree without recursion or stack, possibly by reordering the nodes in a non-recursive manner.

FAQ

How does the in-order traversal help in solving the Convert BST to Greater Tree problem?

In-order traversal visits nodes in increasing order. For this problem, a reverse in-order (right to left) traversal is used to accumulate values of greater nodes first.

What is the time complexity of the Convert BST to Greater Tree problem?

The time complexity is O(N), where N is the number of nodes in the tree, as each node is visited once.

How do you avoid extra space when solving the Convert BST to Greater Tree problem?

By using in-place updates and performing the traversal recursively, you avoid the need for extra data structures, ensuring minimal space usage.

What is the pattern used in Convert BST to Greater Tree?

The problem uses binary-tree traversal with state tracking to accumulate the sum of greater nodes during the traversal.

Can the Convert BST to Greater Tree problem be solved iteratively?

Yes, an iterative solution can be implemented using a stack to simulate the DFS traversal, avoiding recursion.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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
class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def dfs(root):
            nonlocal s
            if root is None:
                return
            dfs(root.right)
            s += root.val
            root.val = s
            dfs(root.left)

        s = 0
        dfs(root)
        return root

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

# 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
class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def dfs(root):
            nonlocal s
            if root is None:
                return
            dfs(root.right)
            s += root.val
            root.val = s
            dfs(root.left)

        s = 0
        dfs(root)
        return root

Continue Practicing

#530 minimum absolute difference in bst #501 find mode in binary search tree #449 serialize and deserialize bst