{x}
blog image

Convert BST to Greater 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 [0, 104].
  • -104 <= Node.val <= 104
  • 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/

Solution Explanation for Convert BST to Greater Tree

This problem requires converting a Binary Search Tree (BST) into a Greater Tree. A Greater Tree is a tree where each node's value is the sum of its original value and all values greater than its original value in the original BST.

There are two main approaches to solving this problem: a recursive approach (Solution 1) and an iterative approach using Morris traversal (Solution 2).

Solution 1: Recursive Approach (In-order Traversal)

This solution leverages the properties of a BST. We perform a reverse in-order traversal (right, root, left). This ensures that we process nodes in decreasing order of their values. We maintain a running sum s, which accumulates the values of all nodes visited so far. As we visit each node, we add its value to s, update the node's value to s, and then recursively process its left subtree.

Time Complexity: O(N), where N is the number of nodes in the BST. This is because we visit each node exactly once during the traversal.

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

Solution 2: Iterative Approach (Morris Traversal)

This solution uses Morris traversal, an in-place algorithm that avoids recursion. Morris traversal cleverly utilizes the left subtree to create a threaded binary tree, effectively simulating the recursive call stack without using extra space for it. Similar to Solution 1, we process nodes in reverse in-order, maintaining a running sum.

Time Complexity: O(N). We visit each node once.

Space Complexity: O(1). We use constant extra space; Morris traversal is in-place.

Code Examples (Python, Java, C++, Go, Javascript):

The code examples provided in the original response demonstrate both approaches. Each language's implementation follows the same core logic described above, adapting the syntax and data structures accordingly. The key differences lie in how recursion is handled (Solution 1) versus the use of iterative techniques (Solution 2) with the while loop and modification of tree pointers in Solution 2. Refer to the original response for the detailed code snippets in each language.

In summary, both solutions correctly solve the problem; however, Solution 2 (Morris Traversal) offers a slight advantage in space complexity, making it more efficient for very large BSTs. Solution 1 (Recursive) is generally easier to understand and implement, especially for those less familiar with tree traversal algorithms. The choice between the two depends on the prioritization of space efficiency versus code readability and simplicity.