{x}
blog image

Binary Search Tree to Greater Sum Tree

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 [1, 100].
  • 0 <= Node.val <= 100
  • All the values in the tree are unique.

 

Note: This question is the same as 538: https://leetcode.com/problems/convert-bst-to-greater-tree/

Solution Explanation:

The problem asks to convert a Binary Search Tree (BST) into a Greater Sum Tree. In a Greater Sum Tree, each node's value is updated to be the sum of all nodes with values greater than or equal to its original value in the BST.

Both solutions presented leverage the property of BSTs: nodes in the right subtree are always greater than the current node. This allows for efficient traversal and summation.

Solution 1: Recursive Depth-First Search (DFS)

This approach uses a recursive depth-first search to traverse the tree in reverse inorder traversal (right, root, left). This order ensures that we process nodes with greater values before smaller values, allowing us to accumulate the sum correctly.

Algorithm:

  1. dfs(root) function: This recursive function performs the following steps:

    • Recursively calls dfs on the right subtree to process larger values first.
    • Adds the current node's value (root.val) to the running sum (s).
    • Updates the current node's value to the accumulated sum (s).
    • Recursively calls dfs on the left subtree.

  2. Main Function:

    • Initializes the running sum s to 0.
    • Calls dfs(root) to start the traversal.
    • Returns the modified root.

Time Complexity: O(N), where N is the number of nodes in the BST. We visit each node exactly once.

Space Complexity: O(H), where H is the height of the BST. This is due to the recursive call stack. In the worst case (a skewed tree), H could be N, resulting in O(N) space complexity. In a balanced BST, H is log₂N.

Solution 2: Iterative Morris Traversal

This approach utilizes the Morris traversal algorithm, an in-place algorithm that avoids recursion and uses constant extra space. It cleverly uses the left subtree to maintain the inorder traversal order without needing an explicit stack.

Algorithm:

  1. Initialization:

    • s is initialized to 0 (the running sum).
    • node is set to the root.

  2. Iteration: The while loop continues as long as there is a node to process:

    • Case 1 (root.right is None): This means we've reached the rightmost node of a subtree. We add the node's value to s, update the node's value to s, and move to the left child.
    • Case 2 (root.right is not None): We find the inorder predecessor (the rightmost node in the left subtree) to link the current node to its inorder successor. This is done efficiently by traversing the right subtree until the leftmost node without a left child. If the predecessor's left child is not the current node (it's NULL), we link the predecessor's left child to the current node and move to the right subtree. If it already points to the current node (it's not NULL), we've already processed the right subtree, so we perform the sum update and move to the left subtree, resetting the link.

  3. Return: The modified root node.

Time Complexity: O(N). Each node is visited and processed exactly once.

Space Complexity: O(1). The algorithm is in-place and uses only a constant amount of extra space.

In summary, Solution 1 is simpler to understand but may use more space for deep trees, while Solution 2 is more optimized in terms of space complexity but slightly more complex to grasp. Both solutions offer correct and efficient solutions to the problem.