Convert BST to Greater Tree
Medium · Graphs · Explanation and code example
Morris Traversal
How it works
Morris traversal allows us to traverse a tree without using extra space for a stack or recursion. It works by temporarily modifying the tree structure to create links back to ancestor nodes, then restoring the original structure. For this problem, we use reverse Morris in-order traversal to visit nodes from largest to smallest while maintaining only O(1) extra space.
Steps
- Initialize a running sum to
0and start at the root. - While the current node is not
null:- If the current node has a right child, find its in-order predecessor in the right subtree (the leftmost node).
- If the predecessor's left child is
null, set it to point to the current node (create a thread) and move to the right child. - If the predecessor's left child points to the current node, remove the thread, process the current node (add to running sum and update value), and move to the left child.
- If there's no right child, process the current node and move to the left child.
- Return the root after all nodes are processed.
Complexity
- Time complexity:
O(n) - Space complexity:
O(1)
Things to watch for
Using Standard In-Order Traversal Instead of Reverse In-Order
Standard in-order traversal visits nodes from smallest to largest. For the Greater Tree, we need to accumulate sums from larger values first, requiring reverse in-order (right, node, left).
Incorrect Order of Update and Accumulation
A subtle bug occurs when you add to curSum before updating the node's value, or update the node before adding the original value to curSum. The sequence must be: save original, update node with accumulated sum, then add original to running sum.
Forgetting to Handle Null Nodes in Recursive Calls
Without a proper base case, the recursion will crash when reaching null children. Always check for null before processing a node.
Python code example
from typing import Optional
# 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 convertBST(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
curSum = 0
cur = root
while cur:
if cur.right:
prev = cur.right
while prev.left and prev.left != cur:
prev = prev.left
if not prev.left:
prev.left = cur
cur = cur.right
else:
prev.left = None
curSum += cur.val
cur.val = curSum
cur = cur.left
else:
curSum += cur.val
cur.val = curSum
cur = cur.left
return root
C++ code example
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
int curSum = 0;
TreeNode* cur = root;
while (cur) {
if (cur->right) {
TreeNode* prev = cur->right;
while (prev->left && prev->left != cur) {
prev = prev->left;
}
if (!prev->left) {
prev->left = cur;
cur = cur->right;
} else {
prev->left = nullptr;
curSum += cur->val;
cur->val = curSum;
cur = cur->left;
}
} else {
curSum += cur->val;
cur->val = curSum;
cur = cur->left;
}
}
return root;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.