Easy_Question24: Convert BST to Greater Tree

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

What is a greater sum tree: 

• A greater sum tree is a tree in which every node contains the sum of all the nodes which are greater than the node.  see the example below

As a reminder, a binary search tree is a tree that satisfies these constraints:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Approach #1 Recursion

class Solution {
    private int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.val;
            root.val = sum;
            convertBST(root.left);
        }
        return root;
    }
}

Complete code  

public class Solution {
    static  int sum = 0; 
   public static class TreeNode
    {
        int data;
        TreeNode left;
        TreeNode right;
        TreeNode(int data)
        {
            this.data=data;
        }
    }

   public static TreeNode insert(TreeNode root,TreeNode nodeToBeInserted){ 
      
      if(root==null) {
         root=nodeToBeInserted; return root;
      } 
      
      if(root.data > nodeToBeInserted.data){
         if(root.left==null)
            root.left=nodeToBeInserted;
         else
            insert(root.left,nodeToBeInserted);
      }
      else if(root.data < nodeToBeInserted.data)
         if(root.right==null)
         root.right=nodeToBeInserted;
         else
         insert(root.right,nodeToBeInserted);
    return root;
    }
 
    public static void inOrder(TreeNode root)
    {
        if(root==null)
            return;
        inOrder(root.left);
        System.out.print(root.data+" ");
        inOrder(root.right);
    }
    public static void main(String[] args)
    {
 
        // Creating a binary search tree
        TreeNode rootNode=createBinarySearchTree();  // Step 1
        convertBST(rootNode); // Step2
        inOrder(rootNode);
    }
 
    public static TreeNode createBinarySearchTree()
    {
        TreeNode rootNode =new TreeNode(4);
        TreeNode node0=new TreeNode(0);
        TreeNode node1=new TreeNode(1);
        TreeNode node2=new TreeNode(2);
        TreeNode node3=new TreeNode(3);
        TreeNode node5=new TreeNode(5);
        TreeNode node6=new TreeNode(6);
        TreeNode node7=new TreeNode(7);
        TreeNode node8=new TreeNode(8);
 
        insert(null,rootNode);
        insert(rootNode,node1);
        insert(rootNode,node6);
        insert(rootNode,node0);
        insert(rootNode,node2);
        insert(rootNode,node5);
        insert(rootNode,node7);
        insert(rootNode,node3);
        insert(rootNode,node8);
        return rootNode;
    }
   
     public static TreeNode convertBST(TreeNode root) {
        if (root != null) {
            convertBST(root.right);
            sum += root.data;
            root.data = sum;
            convertBST(root.left);
        }
        return root;
    }
}

Complexity Analysis

• Time complexity : 
  $\mathcal{O}(n)$

• Space complexity : 
  $\mathcal{O}(n)$

Step 1 visualizer 

Step 2 visualizer 

---

Approach #2 Reverse Morris In-order Traversal

class Solution {
    /* Get the node with the smallest value greater than this one. */
    private TreeNode getSuccessor(TreeNode node) {
        TreeNode succ = node.right;
        while (succ.left != null && succ.left != node) {
            succ = succ.left;
        }
        return succ;
    }

    public TreeNode convertBST(TreeNode root) {
        int sum = 0;
        TreeNode node = root;

        while (node != null) {
            /* 
             * If there is no right subtree, then we can visit this node and
             * continue traversing left.
             */
            if (node.right == null) {
                sum += node.val;
                node.val = sum;
                node = node.left;
            }
            /* 
             * If there is a right subtree, then there is at least one node that
             * has a greater value than the current one. therefore, we must
             * traverse that subtree first.
             */
            else {
                TreeNode succ = getSuccessor(node);
                /* 
                 * If the left subtree is null, then we have never been here before.
                 */
                if (succ.left == null) {
                    succ.left = node;
                    node = node.right;
                }
                /* 
                 * If there is a left subtree, it is a link that we created on a
                 * previous pass, so we should unlink it and visit this node.
                 */
                else {
                    succ.left = null;
                    sum += node.val;
                    node.val = sum;
                    node = node.left;
                }
            }
        }
        
        return root;
    }
}

Complexity Analysis
Time complexity : O(n)
Space complexity : O(1)