Transform a BST to greater sum tree

Transform a BST to greater sum tree

Here given code implementation process.

//C Program 
//Transform a BST to greater sum tree
#include <stdio.h>
#include <stdlib.h>
//structure of Binary Search Tree node
struct Node
{
  int data;
  struct Node *left,*right; 
};

//Adding a new node in binary search tree
void add( struct Node **root, int data)
{
  //Create a dynamic node of binary search tree 
  struct Node *new_node = (struct Node *)malloc(sizeof(struct Node ));

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(*root == NULL)
    {
      //When adds a first node in binary tree
      *root = new_node;
    }
    else
    {
      struct Node *find = *root;
      //iterate binary tree and add new node to proper position
      while(find != NULL)
      {
        if(find -> data > data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }else
  {
    printf("Memory Overflow\n");
    exit(0); //Terminate program execution
  }

}

//Convert BST to greater sum tree
int convert(struct Node*root,int *prev)
{
  if(root != NULL)
  {
    
    convert(root->right,prev);
      
      int temp=*prev;

      *prev+=root->data;
      //set new data value
      root->data= temp;
     
    convert(root->left,prev);
  
  }
}
void inorder(struct Node*root)
{
  if(root!=NULL)
  {
    
    inorder(root->left);
    printf("%3d ",root->data );
    inorder(root->right);
  }
}
int main(){
    
  struct Node*root = NULL;

  //Add nodes in binary search tree
  /*
              5
           /    \
          3       8
         / \     / \
        2   4   6   11
       /            /
      1            10 

  */                

  add(&root,5); 
  add(&root,3); 
  add(&root,8); 
  add(&root,2); 
  add(&root,4); 
  add(&root,6); 
  add(&root,11); 
  add(&root,1);  
  add(&root,10); 

  
  inorder(root);
  int prev=0;
  convert(root,&prev);
  /*
              35
           /     \
          44      21
         / \     /   \
        47  40  29    0
       /             /
      49            11   
  */
  printf("\n");
  inorder(root);
  return 0;
}

Output

  1   2   3   4   5   6   8  10  11 
 49  47  44  40  35  29  21  11   0 
//C++ Program 
//Transform a BST to greater sum tree
#include <iostream>
using namespace std;

//Structure of Binary Search Tree node
struct Node
{
  int data;
  Node *left,*right; 
};

class BST
{

public:
  Node*root;
  BST();
  //public methods
  void add(int);
  void inorder(Node*);
  int convert(Node*,int *);
};
BST::BST()
{
  root=NULL;
}
//Adding a new node in binary search tree
void BST :: add(int data)
{
  //Create a dynamic node of binary search tree 
   Node *new_node = new Node();

  if(new_node!=NULL)
  {
    //Set data and pointer values
    new_node->data = data;
    new_node->left = NULL; //Initially node left-pointer is NULL
    new_node->right = NULL;//Initially node right-pointer is NULL

    if(root == NULL)
    {
      //When adds a first node in binary tree
      root = new_node;
    }
    else
    {
       Node *find = root;

      //add new node to proper position
      while(find != NULL)
      {
        if(find -> data >= data)
        { 
          if(find->left==NULL)
          {
            find->left = new_node;
            break;
          }
          else
          { 
            //visit left sub-tree
            find = find->left;
          }
        }
        else
        {
          if(find->right == NULL)
          {
            find->right = new_node;
            break;
          }
          else
          {
            //visit right sub-tree
            find = find->right;
          }
        }
      }
    }
  }
  else
  {
    cout<<("Memory Overflow\n");
  }
}
//Convert BST to greater sum tree
int BST :: convert(struct Node*root,int *prev)
{
  if(root != NULL)
  {
    
    convert(root->right,prev);
      
      int temp=*prev;

      *prev+=root->data;
      //set new data value
      root->data= temp;
     
    convert(root->left,prev);
  
  }
}
void BST :: inorder(Node*root)
{
  if(root!=NULL)
  {

    inorder(root->left);
    cout<<"  "<< root->data;
    inorder(root->right);
  }
}

int main()
{
  //Create object
  BST obj;



  //Add nodes in binary search tree
  /*
         5
       /   \
      3     8
     / \   / \
    2   4  6  11
   /          /
  1          10 
  */  
  obj.add(5); 
  obj.add(3); 
  obj.add(8); 
  obj.add(2); 
  obj.add(4); 
  obj.add(6); 
  obj.add(11); 
  obj.add(1);  
  obj.add(10); 

  obj.inorder(obj.root);
  int prev=0;
  obj.convert(obj.root,&prev);
  /*
        35
       /   \
      44    21
     / \    /  \
    47 40  29   0
   /           /
  49          11  
  */
  cout<<("\n");
  obj.inorder(obj.root);


  return 0;
}

Output

  1  2  3  4  5  6  8  10  11
  49  47  44  40  35  29  21  11  0
//Java program
//Transform a BST to greater sum tree
public class BST
{

  static class Node
  {
    int data;
    Node left,right;
  }
  public Node root;
  public int prev;
  //Class constructors
  BST()
  {
    root=null;
    prev=0;
  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = null;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
            //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      System.out.println("Memory Overflow");
    }
  }
  //Convert BST to greater sum tree
  public void convert(Node root)
  {
    if(root != null)
    {

      convert(root.right);
      
      int temp= prev;

      prev+=root.data;
      //set new data value
      root.data= temp;

      convert(root.left);

    }
  }
  public void sum_tree()
  {
    prev=0;
    convert(root);
  }

  public void inorder(Node root)
  {
    if(root!=null)
    {

      inorder(root.left);
      System.out.print("  "+ root.data);
      inorder(root.right);
    }
  }


  public static void main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /* 
           5
         /   \
        3     8
       / \   / \
      2   4  6  11
     /          /
    1          10 
    */  
    obj.add(5); 
    obj.add(3); 
    obj.add(8); 
    obj.add(2); 
    obj.add(4); 
    obj.add(6); 
    obj.add(11); 
    obj.add(1);  
    obj.add(10); 

    obj.inorder(obj.root);
   
    obj.sum_tree();
    /* 
          35
         /   \
        44    21
       / \    /  \
      47 40  29   0
     /           /
    49          11  
    */
    System.out.println("\n");
    obj.inorder(obj.root);

  }
}

Output

  1  2  3  4  5  6  8  10  11

  49  47  44  40  35  29  21  11  0
#Python Program 
#Transform a BST to greater sum tree
class Node:
  def __init__(self,data):
    self.data=data
    self.left=None
    self.right=None

   
class BST:

  def __init__(self):

    #Assign default value
    self.root=None
    self.prev=0
  
  #insert  element
  def add(self,data):

    #Create a dynamic node of binary search tree 
    new_node = Node(data)

    if(self.root == None):
      #When adds a first node in binary tree
      self.root = new_node
    
    else:
      find = self.root

      #add new node to proper position
      while(find != None):

        if(find.data >= data): 

          if(find.left==None):

            find.left = new_node
            break
          
          else: 

            #visit left sub-tree
            find = find.left
          
        
        else:

          if(find.right == None):

            find.right = new_node
            break
          
          else:

            #visit right sub-tree
            find = find.right
  
  def inorder(self, root):

    if(root!=None):

      self.inorder(root.left)
      print(root.data,end="  ")
      self.inorder(root.right)
    

  #Convert BST to greater sum tree
  def  convert(self,root) :

    if(root!= None) :

      self.convert(root.right)
      temp=self.prev
      self.prev+= root.data
      #set new data value
      root.data= temp
      self.convert(root.left)
  
  def sum_tree(self) :

    self.prev=0
    self.convert(self.root)

def main():
  obj = BST()



  # Add nodes in binary search tree
  #  
  #          5
  #        /   \
  #       3     8
  #      /\    / \
  #     2  4  6   11
  #    /         /
  #   1         10 
  #   
  obj.add(5) 
  obj.add(3) 
  obj.add(8) 
  obj.add(2) 
  obj.add(4) 
  obj.add(6) 
  obj.add(11) 
  obj.add(1)  
  obj.add(10) 
  obj.inorder(obj.root)

  obj.sum_tree()
  #  
  #         35
  #        /   \
  #       44    21
  #      /  \   / \
  #     47  40 29  0
  #    /          /
  #   49         11  
  #   
  print ("\n")
  obj.inorder(obj.root)

if __name__ =="__main__":
  main()

Output

1  2  3  4  5  6  8  10  11  

49  47  44  40  35  29  21  11  0 
//C# program
//Transform a BST to greater sum tree
using System;

public class Node
{
  public int data;
  public Node left,right;
}
public class BST
{
  
  public Node root;
  public int prev;
  //Class constructors
  BST()
  {
    root=null;
    prev=0;
  } 

  //insert  element
  public void add(int data)
  {
    //Create a dynamic node of binary search tree 
    Node new_node = new Node();

    if(new_node != null)
    {
      //Set data and pointer values
      new_node.data = data;
      //Initially node left-pointer is null
      new_node.left = null; 
      //Initially node right-pointer is null
      new_node.right = null;

      if(root == null)
      {
        //When adds a first node in binary tree
        root = new_node;
      }
      else
      {
        Node find = root;

        //add new node to proper position
        while(find != null)
        {
          if(find.data >= data)
          { 
            if(find.left==null)
            {
              find.left = new_node;
              break;
            }
            else
            { 
              //visit left sub-tree
              find = find.left;
            }
          }
          else
          {
            if(find.right == null)
            {
              find.right = new_node;
              break;
            }
            else
            {
              //visit right sub-tree
              find = find.right;
            }
          }
        }
      }
    }
    else
    {
      Console.WriteLine("Memory Overflow");
    }
  }
  //Convert BST to greater sum tree
  public void convert(Node root)
  {
    if(root != null)
    {

      convert(root.right);

      int temp= prev;

      prev+=root.data;
      //set new data value
      root.data= temp;

      convert(root.left);

    }
  }
  public void sum_tree()
  {
    prev=0;
    convert(root);
  }

  public void inorder(Node root)
  {
    if(root!=null)
    {

      inorder(root.left);
      Console.Write("  "+ root.data);
      inorder(root.right);
    }
  }


  public static void Main(String[] args) 
  {

    BST obj = new BST();

    //Add nodes in binary search tree
    /* 
             5
           /   \
          3     8
         / \   / \
        2   4  6  11
       /          /
      1          10 
      */  
    obj.add(5); 
    obj.add(3); 
    obj.add(8); 
    obj.add(2); 
    obj.add(4); 
    obj.add(6); 
    obj.add(11); 
    obj.add(1);  
    obj.add(10); 

    obj.inorder(obj.root);

    obj.sum_tree();
    /* 
            35
           /   \
          44    21
         / \    /  \
        47 40  29   0
       /           /
      49          11  
      */
    Console.WriteLine("\n");
    obj.inorder(obj.root);

  }
}

Output

  1  2  3  4  5  6  8  10  11

  49  47  44  40  35  29  21  11  0
<?php
//Php program 
//Transform a BST to greater sum tree
class Node
{
  public $data;
  public $left;
  public $right;
  function __construct($data)
  {
    $this->data = $data;
    $this->length = NULL;
    $this->right = NULL;
  }
}
class BST
{

  public $root;
  function __construct()
  {
    $root=NULL;
  }
  //Adding a new node in binary search tree
  public function add($data)
  {
    //Create a dynamic node of binary search tree 
    $new_node = new Node($data);

    if($this->root == NULL)
    {
      //When adds a first node in binary tree
      $this->root = $new_node;
    }
    else
    {
      $find = $this->root;

      //add new node to proper position
      while($find != NULL)
      {
        if($find->data >= $data)
        { 
          if($find->left==NULL)
          {
            $find->left = $new_node;
            break;
          }
          else
          { 
          //visit left sub-tree
            $find = $find->left;
          }
        }
        else
        {
          if($find->right == NULL)
          {
            $find->right = $new_node;
            break;
          }
          else
          {
          //visit right sub-tree
            $find = $find->right;
          }
        }
      }
    }

  }

  public function inorder($root)
  {
    if($root!=NULL)
    {

      $this->inorder($root->left);
      echo "  ". $root->data;
      $this->inorder($root->right);
    }
  }


  //Convert BST to greater sum tree
  public function convert($root,&$prev)
  {
    if($root!= NULL)
    {

      $this->convert($root->right,$prev);

      $temp=$prev;

      $prev+= $root->data;
      //set new data value
      $root->data= $temp;

      $this->convert($root->left,$prev);

    }
  }


}
function main()
{
  //Make a object of BST class
  $obj= new BST();


  

  # Add nodes in binary search tree
  #  
  #          5
  #        /   \
  #       3     8
  #      /\    / \
  #     2  4  6   11
  #    /         /
  #   1         10 
  #   
  $obj->add(5); 
  $obj->add(3); 
  $obj->add(8); 
  $obj->add(2); 
  $obj->add(4); 
  $obj->add(6); 
  $obj->add(11); 
  $obj->add(1);  
  $obj->add(10); 

  $obj->inorder($obj->root);
  $prev=0;
  $obj->convert($obj->root,$prev);
  #  
  #         35
  #        /   \
  #       44    21
  #      /  \   / \
  #     47  40 29  0
  #    /          /
  #   49         11  
  #   
  echo ("\n");
  $obj->inorder($obj->root);

}
main();
?>

Output

  1  2  3  4  5  6  8  10  11
  49  47  44  40  35  29  21  11  0


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved