Binary Search Tree to Greater Sum Tree

1038. Binary Search Tree to Greater Sum Tree

DFS

Intuition

When we have node at the right, we traverse and add it.

When we have node at the left, add the right side first, then add node->val + right side val to the left.

Code

cpp

TreeNode* bstToGst(TreeNode* root) {
    int tp = 0;
    solve(root,tp);
    return root;
}

void solve(TreeNode* root, int& higher) {
    if(!root)
        return;
    if(root->right)
        solve(root->right,higher);
    root->val += higher;
    higher = root->val;
    if(root->left)
        solve(root->left,higher);
}

Complexity Analysis

Time : O(n)

Space : O(1)

Binary Search Tree to Greater Sum Tree ​

DFS ​

Intuition ​

Code ​

Complexity Analysis ​

Binary Search Tree to Greater Sum Tree

DFS

Intuition

Code

Complexity Analysis