Convert BST to Greater Tree

Medium

Asked by:

20 views

Topics:

TreesRecursion

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:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

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:

The number of nodes in the tree is in the range [0, 10⁴].
-10⁴ <= Node.val <= 10⁴
All the values in the tree are unique.
root 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/

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the nodes in the BST? Can they be negative, zero, or very large?
Could the input BST be empty (null)? What should I return in that case?
Are there duplicate values in the BST? If so, how should they be handled during the conversion?
Is the input guaranteed to be a valid Binary Search Tree?
Should the original BST structure be modified in-place, or should I create a new tree with the converted values?

Brute Force Solution

Approach

The goal is to change a tree so that each value also includes the sum of all values bigger than it. The brute force method figures this out by looking at each value separately and recalculating the sum of larger values every single time.

Here's how the algorithm would work step-by-step:

For each value in the tree, we need to find all the other values in the tree that are larger.
To do this, we go through every single value in the entire tree and check if it is bigger than the current value we are looking at.
If we find a value that is bigger, we add it to a running total.
Once we've checked every value in the entire tree against our starting value, that running total becomes the new value for our starting value.
Repeat this process for every single value in the tree, updating each one individually with the sum of all the values larger than it.

Code Implementation

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

def convert_bst_to_greater_tree_brute_force(root):
    if not root:
        return root

    def get_all_node_values(root):
        all_values = []
        if root:
            all_values.append(root.val)
            all_values.extend(get_all_node_values(root.left))
            all_values.extend(get_all_node_values(root.right))
        return all_values

    all_node_values = get_all_node_values(root)

    def update_node_values(root, all_node_values):
        if root:
            original_node_value = root.val
            greater_sum = 0
            # Calculate the sum of all values greater than current node's value
            for value in all_node_values:
                if value > original_node_value:
                    greater_sum += value

            root.val = original_node_value + greater_sum

            update_node_values(root.left, all_node_values)
            update_node_values(root.right, all_node_values)

    update_node_values(root, all_node_values)
    return root

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through each of the n nodes in the tree. For each node, it then traverses the entire tree again, comparing every other node to the current node to determine if it's larger. This nested iteration results in roughly n operations for each of the n nodes, leading to a time complexity proportional to n * n. Therefore, the overall time complexity is O(n²).

Space Complexity

O(1) – The described brute force method iterates through the tree multiple times to compare each node with every other node. It appears to only use a few variables to store the current node's value, the comparison node's value, and a running sum of larger values. No auxiliary data structures that scale with the input size N (the number of nodes in the tree) are mentioned. Therefore, the space complexity is constant, O(1).

Optimal Solution

Approach

The key idea is to traverse the tree in a special order: right, node, left. While traversing, we keep track of a running sum of all the node values we've seen so far, and update each node's value with this sum.

Here's how the algorithm would work step-by-step:

Start at the rightmost node of the tree. This node will have the largest value in the BST.
Keep track of a running total, initially set to zero.
Add the value of the rightmost node to the running total, and then update the rightmost node's value with this new running total.
Move to the parent node of the rightmost node.
Add the value of this parent node to the running total, and update the parent's value with the new running total.
Now, process the right subtree of this parent node. This will involve recursively applying these steps to the right subtree.
After processing the right subtree, move to the left child of the parent node (if it exists).
Add the value of this left child to the running total, and update the left child's value with the new running total.
Recursively apply these steps to the left child subtree.
Continue this right, node, left traversal, updating the running total and node values as you go, until the entire tree has been visited.

Code Implementation

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:
        running_sum = 0

        def traverse_right_node_left(root_node):
            nonlocal running_sum

            if not root_node:
                return

            # Traverse the right subtree first
            traverse_right_node_left(root_node.right)

            # Update running sum and node value
            running_sum += root_node.val
            root_node.val = running_sum

            # Traverse the left subtree after updating the node
            traverse_right_node_left(root_node.left)

        #Start the traversal from the root.
traverse_right_node_left(root)

        return root

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each node in the binary search tree exactly once. The key operation is the right, node, left traversal, which ensures every node is touched. Updating the running sum and the node's value takes constant time for each node. Therefore, the time complexity is directly proportional to the number of nodes, n, in the BST.

Space Complexity

O(H) – The algorithm's space complexity is determined by the recursion depth of the call stack during the traversal. In the worst-case scenario, where the BST is skewed (resembling a linked list), the recursion depth can be equal to the height (H) of the tree, which could be N (the number of nodes) in the worst case. Thus, the auxiliary space is primarily used by the call stack, with a maximum depth proportional to the tree's height, H. Therefore, the space complexity is O(H), which simplifies to O(N) in the worst case for skewed trees, and O(log N) for balanced trees.

Edge Cases

Case	How to Handle
Null root	Return null immediately, as there's nothing to convert.
Single node tree	The node's value remains unchanged as there are no greater values to add.
Tree with all nodes having the same value	Each node will be updated to the tree's value times the number of nodes, due to iterative addition during the traversal.
Skewed tree (e.g., all nodes on the right side)	The rightmost node will keep its original value, and other node's value will be updated according to the right side values.
Skewed tree (e.g., all nodes on the left side)	All nodes will be updated with the cumulative sum of nodes from right to left.
Tree with negative values	The algorithm will handle negative values correctly, as it's based on summing the node values in reverse inorder traversal.
Integer overflow if node values are large	Consider using a larger integer type (e.g., long) or handling potential overflows to prevent incorrect sums.
Large BST causing stack overflow with recursive approach	Convert recursive solution to iterative approach using stack to avoid stack overflow

Null root

How to Handle:

Return null immediately, as there's nothing to convert.

Single node tree

How to Handle:

The node's value remains unchanged as there are no greater values to add.

Tree with all nodes having the same value

How to Handle:

Each node will be updated to the tree's value times the number of nodes, due to iterative addition during the traversal.

Skewed tree (e.g., all nodes on the right side)

How to Handle:

The rightmost node will keep its original value, and other node's value will be updated according to the right side values.

Skewed tree (e.g., all nodes on the left side)

How to Handle:

All nodes will be updated with the cumulative sum of nodes from right to left.

Tree with negative values

How to Handle:

The algorithm will handle negative values correctly, as it's based on summing the node values in reverse inorder traversal.

Integer overflow if node values are large

How to Handle:

Consider using a larger integer type (e.g., long) or handling potential overflows to prevent incorrect sums.

Large BST causing stack overflow with recursive approach

How to Handle:

Convert recursive solution to iterative approach using stack to avoid stack overflow