Convert BST to Greater Tree - Video Solutions
Convert BST to Greater Tree - Leetcode 538 - Python
Convert BST to Greater Tree - Video Solution
Watch 10 video solutions for Convert BST to Greater Tree, a medium level problem involving Tree, Depth-First Search, Binary Search Tree. This walkthrough by NeetCode has 28,226 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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.
rootis 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/
Approach Overview
Problem Overview: You are given a Binary Search Tree where each node must be updated to contain its original value plus the sum of all keys greater than it. The BST ordering property (left < root < right) is the key observation that makes the problem solvable efficiently.
Approach 1: Reverse Inorder Traversal (O(n) time, O(h) space)
A Binary Search Tree visited in normal inorder produces values in ascending order. Reversing the order (right → root → left) processes nodes from largest to smallest. Maintain a running sum of visited node values. When visiting a node, add the running sum to its value, then update the sum. This works because every node encountered earlier in reverse inorder is guaranteed to have a greater value. The traversal can be implemented using recursion or an explicit stack via depth-first search. Time complexity is O(n) since every node is visited once, and auxiliary space is O(h) where h is the tree height due to the recursion stack.
Approach 2: Morris Traversal (O(n) time, O(1) space)
Morris traversal eliminates the recursion stack by temporarily modifying tree pointers during traversal. For this problem, perform a reverse Morris traversal (right → root → left). For each node, locate its inorder successor and create a temporary threaded link back to the current node. This allows returning after exploring the right subtree without a stack. Maintain the same running sum logic used in the DFS solution. After processing, restore all modified pointers so the tree structure remains intact. The traversal still visits each node a constant number of times, giving O(n) time and O(1) extra space. This approach is useful when strict memory constraints exist or when recursion depth might become large.
Recommended for interviews: Reverse inorder traversal is the solution most interviewers expect. It directly leverages the tree ordering property and is easy to reason about. Mentioning Morris traversal shows deeper knowledge of traversal optimization and space reduction, but the recursive DFS approach usually communicates the core insight more clearly during interviews.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Reverse Inorder Traversal (DFS) | O(n) | O(h) | Standard interview solution. Simple recursion leveraging BST ordering. |
| Morris Reverse Traversal | O(n) | O(1) | Useful when minimizing auxiliary memory or avoiding recursion stack. |