Formatted question description: https://leetcode.ca/all/538.html

538. Convert BST to Greater Tree

Level

Easy

Description

Given 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 sum of all keys greater than the original key in BST.

Example:

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

Solution

First obtain the inorder traversal of the binary search tree. The inorder traversal contains all the nodes of the binary search tree with the nodes sorted according to their values.

Loop over the inorder traversal backward, with the last node (the original node in the binary search tree with the greatest value) skipped. For each node, obtain its next node in the inorder traversal (here “next” is in the forward direction), and add its next node’s value to the value of itself. After the operation, the node’s value is changed to the original value plus sum of all values greater than the original value in binary search tree.

Finally, return the root.

public class Convert_BST_to_Greater_Tree {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {

        int sum = 0;

        public TreeNode convertBST(TreeNode root) {
            if (root == null) {
                return null;
            }

            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);

            return root;
        }
    }
}

All Problems

All Solutions