Monday, March 1, 2021
More

    Convert BST to Greater Tree

    Must Read

    Programmerhttp://www.improgrammer.net
    We started this site to inspire young minds to motivate and encourage them towards Programming Language. In this site you will get programming tutorials, tech, programming facts, programming fun and programming blogs.
    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. Let’s Convert BST to Greater Tree.

    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


    Approach 1:  Using Reversed inorder traversal.
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
      public TreeNode convertBST(TreeNode root) {
         if(root==null){
             return root;
         }else{
              DFS (root,0);
         }
         return root;
      }
    
         public int DFS(TreeNode root, int presum){
             if(root.right!=null){
                   presum=DFS(root.right,presum);
              }
              root.val+=presum;
    
         return (root.left!=null?DFS(root.left,root.val):root.val);
         }
    }

     
    Best Approach:
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    public class Solution {
     int sum=0;
           public TreeNode convertBST(TreeNode root) {
    
         helper(root);
         return root;
         }
         public void helper(TreeNode root){
             if(root==null)return;
              helper(root.right);
              sum=sum+root.val;
              root.val=sum;
              helper(root.left);
         }
    }

     

    Latest Articles

    More Recipes Like This