Sponsored
Sponsored
This approach leverages the property of Binary Search Trees where the nodes in the right subtree are greater than those in the left subtree. By performing a reverse inorder traversal (right -> root -> left), we can accumulate the sum of all nodes greater than the current node and update each node with this accumulated sum. The traversal ensures that we always process the greater nodes first.
Time Complexity: O(n), where n is the number of nodes in the BST, since we visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree, due to the recursion stack used during traversal.
1#include <iostream>
2
3struct TreeNode {
4 int val;
5 TreeNode *left;
6 TreeNode *right;
7 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8};
9
10class Solution {
11 int sum = 0;
12public:
13 TreeNode* convertBST(TreeNode* root) {
14 if (root != NULL) {
15 convertBST(root->right);
16 sum += root->val;
17 root->val = sum;
18 convertBST(root->left);
19 }
20 return root;
21 }
22};The C++ solution makes use of a class, Solution, which contains an integer member sum. The function convertBST is then a method of this class. The method updates the tree by performing a reverse inorder traversal, updating each node's value with the accumulated sum of all greater nodes.
The Morris Traversal technique allows in-order traversal of a binary tree without using extra space for recursion or a stack. It modifies the tree structure during the traversal, and at the end of the traversal, the original tree structure is restored.
For this problem, we adapt the Morris Traversal to traverse the tree in reverse inorder fashion and keep track of the sum of nodes greater than the current node.
Time Complexity: O(n), where n is the number of nodes. Although every edge is visited at most twice, the overall complexity remains linear.
Space Complexity: O(1) since no extra space is used apart from variables.
1class TreeNode:
2 def __init__(self, val=0,
This Python solution uses the Morris Traversal technique, which allows modifying the tree without using stack or recursion explicitly. The key idea is to establish a temporary link between each node and its inorder predecessor, traverse in reverse inorder, update the nodes, and then restore the tree structure by removing the temporary links.