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.


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

Output: The root of a Greater Tree like this:
            /   \
          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;}
      return root;
    public static void convert(TreeNode node) {
       if (node == null) {return;}
       sum += node.val;
       node.val = sum;


   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.


Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s