We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Binary Search Tree to Greater Sum Tree

Number: 1114

Difficulty: Medium

Paid? No

Companies: Amazon, SAP, eBay

Problem Description

Given the root of a Binary Search Tree (BST), convert it into 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 the BST.

Key Insights

  • Utilize the properties of BST where the right subtree contains larger values.
  • Traverse the tree in reverse in-order (right, node, left) to accumulate the sum of greater values.
  • Maintain an accumulator to update each node's value as you traverse.

Space and Time Complexity

Time Complexity: O(n) - every node is visited once.
Space Complexity: O(h) - where h is the height of the tree; in the worst-case scenario (skewed tree), it can be O(n).

Solution

The solution employs a reverse in-order depth-first traversal:

  • Start with the rightmost (largest) node.
  • Use an accumulator variable to keep track of the total sum of visited nodes.
  • For each node visited, add its value to the accumulator, then update the node's value with the accumulator.
  • Continue to the left subtree.
  • This traversal takes advantage of the BST structure, ensuring that at each node, the accumulator holds the sum of all nodes that have greater values.

Code Solutions

# 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 bstToGst(self, root: TreeNode) -> TreeNode:
        # Initialize the accumulator to keep track of the sum of nodes visited so far
        self.accumulator = 0
        
        # Define a recursive function to traverse the tree in reverse in-order
        def reverseInorder(node: TreeNode):
            if not node:
                return
            # First, traverse the right subtree (larger values)
            reverseInorder(node.right)
            # Update the accumulator and node's value
            self.accumulator += node.val
            node.val = self.accumulator
            # Then, traverse the left subtree
            reverseInorder(node.left)
        
        # Start the reverse in-order traversal from the root
        reverseInorder(root)
        return root
← Back to All Questions