BST to Greater Tree

Posted on Updated on

/*
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
*/

public class convertBST{
   static int sum = 0; // trace the sum of previous nodes
   public static TreeNode convertBST(TreeNode root) {
      if (root == null) {return null;}
      convert(root);
      return root;
    }
    public static void convert(TreeNode node) {
       if (node == null) {return;}
       convert(node.right);
       sum += node.val;
       node.val = sum;
       convert(node.left);

    }

   public static void main(String[] args) {

   }
}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

In a BST, every node only needs to add the values of nodes on the right. So use recursion to find the rightmost node first. Use a variable “sum” to store the accumulating values. Each time use “sum” to replace current value. Nothing to be accumulated to the left side.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s