BST to a tree with sum of all smaller keys

Here given code implementation process.

/*
    C program for
    BST to a tree with sum of all smaller keys
*/
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
};
// Binary Search Tree
struct BinarySearchTree
{
    struct TreeNode *root;
};

// Create new tree
struct BinarySearchTree *newTree()
{
    // Create dynamic node
    struct BinarySearchTree *tree = (struct BinarySearchTree *) 
                                malloc(sizeof(struct BinarySearchTree));
    if (tree != NULL)
    {
        tree->root = NULL;
    }
    else
    {
        printf("Memory Overflow to Create tree Tree\n");
    }
    // Return new tree
    return tree;
}
// This is creates and returns the new binary search tree node
struct TreeNode *getNode(int data)
{
    // Create dynamic node
    struct TreeNode *node = (struct TreeNode *) malloc(sizeof(struct TreeNode));
    if (node != NULL)
    {
        // Set data and pointer values
        node->data = data;
        node->left = NULL;
        node->right = NULL;
    }
    else
    {
        // This is indicates, 
        // Segmentation fault or memory overflow problem
        printf("Memory Overflow\n");
    }
    //return new node
    return node;
}
// Recursive function
// Display preorder view of binary search tree
void preorder(struct TreeNode *node)
{
    if (node!=NULL)
    {
        // Print node value
        printf("  %d", node->data);
        preorder(node->left);
        preorder(node->right);
    }
}
// Adding a new node in binary search tree
void addNode(struct BinarySearchTree *tree, int data)
{
    struct TreeNode *node = getNode(data);
    if (node != NULL)
    {
        if (tree->root == NULL)
        {
            tree->root = node;
        }
        else
        {
            struct TreeNode *auxiliary = tree->root;
            // Add new node in binary search tree
            while (auxiliary != NULL)
            {
                if (data > auxiliary->data)
                {
                    if (auxiliary->right == NULL)
                    {
                        // Add new node at right child
                        auxiliary->right = node;
                        return;
                    }
                    auxiliary = auxiliary->right;
                }
                else
                {
                    if (auxiliary->left == NULL)
                    {
                        // Add new node at left child
                        auxiliary->left = node;
                        return;
                    }
                    auxiliary = auxiliary->left;
                }
            }
        }
    }
}
void replace(struct TreeNode *node, int *sum)
{
    if (node!=NULL)
    {
        // Visit left subtree
        replace(node->left,sum);
        // Add node value
        *sum = *sum + node->data;
        // Change node value
        node->data = *sum;
        // Visit right subtree
        replace(node->right,sum);
    }
}
void replaceBySmaller(struct TreeNode *node)
{
    int sum = 0;

    replace(node,&sum);
}
int main()
{
    struct BinarySearchTree *tree = newTree();
    /*
             6                            
           /   \    
          3     7    
         / \     \               
        2   4     12
       /     \    / 
      1       5  9
    -----------------
        Binary Search Tree
    */
    addNode(tree,6);
    addNode(tree,3);
    addNode(tree,4);
    addNode(tree,5);
    addNode(tree,2);
    addNode(tree,1);
    addNode(tree,7);
    addNode(tree,12);
    addNode(tree,9);


    printf("\n Before Tree Element : ");
    preorder(tree->root);
    /*
          (15+6)

             21  
            /   \                          
    (1+2+3)/     \    
          6       28  (21+7)
         / \       \ 
        /   \       \               
  (1+2)3    10(6+4)  49(37+12)
      /       \      / 
     /         \    /
    1          15  37
            (10+5) (28+9)
    -----------------
      Resultant Binary Search Tree
    */
    replaceBySmaller(tree->root);

    printf("\n After Tree Element : ");
    preorder(tree->root);
    return 0;
}

Output

 Before Tree Element :   6  3  2  1  4  5  7  12  9
 After Tree Element :   21  6  3  1  10  15  28  49  37
/*
    Java Program for
    BST to a tree with sum of all smaller keys
*/
class TreeNode
{
    // Data value 
    public int data;
    // Indicates left and right subtree
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinarySearchTree 
{
    public TreeNode root;
    public int sum;
    public BinarySearchTree()
    {
        this.root = null;
        this.sum  = 0;
    }
    // insert a node in BST
    public void addNode(int data)
    {
        // Create new node of tree
        TreeNode node = new TreeNode(data);

        if (this.root == null)
        {
            this.root = node;
        }
        else
        {
            TreeNode auxiliary = this.root;
            // Add new node in binary search tree
            while (auxiliary != null)
            {
                if (data > auxiliary.data)
                {
                    if (auxiliary.right == null)
                    {
                        // Add new node at right child
                        auxiliary.right = node;
                        return;
                    }
                    auxiliary = auxiliary.right;
                }
                else
                {
                    if (auxiliary.left == null)
                    {
                        // Add new node at left child
                        auxiliary.left = node;
                        return;
                    }
                    auxiliary = auxiliary.left;
                }
            }
        }
    }
    // Recursive function
    // Display preorder view of binary search tree
    public void preorder(TreeNode node)
    {
        if (node != null)
        {
            // Print node value
            System.out.print(" " + node.data );
            preorder(node.left);
            preorder(node.right);
        }
    }
    public void replace(TreeNode node)
    {
        if (node != null)
        {
            // Visit left subtree
            replace(node.left);
            // Add node value
            this.sum = this.sum + node.data;
            // Change node value
            node.data = this.sum;
            // Visit right subtree
            replace(node.right);
        }
    }
    public void replaceBySmaller()
    {
        this.sum = 0;

        this.replace(this.root);

    }
    public static void main(String[] args) 
    {
        BinarySearchTree tree = new BinarySearchTree();
        /*
                 6                            
               /   \    
              3     7    
             / \     \               
            2   4     12
           /     \    / 
          1       5  9
        -----------------
            Binary Search Tree
        */
        tree.addNode(6);
        tree.addNode(3);
        tree.addNode(2);
        tree.addNode(1);
        tree.addNode(4);
        tree.addNode(5);
        tree.addNode(7);
        tree.addNode(12);
        tree.addNode(9);

        System.out.print("\n Before Tree Element : ");
        tree.preorder(tree.root);
        /*
              (15+6)

                 21  
                /   \                          
        (1+2+3)/     \    
              6       28  (21+7)
             / \       \ 
            /   \       \               
      (1+2)3    10(6+4)  49(37+12)
          /       \      / 
         /         \    /
        1          15  37
                (10+5) (28+9)
        -----------------
        Resultant Binary Search Tree
        */
        tree.replaceBySmaller();
        System.out.print("\n After Tree Element : ");
        tree.preorder(tree.root);

    }
}

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37
// Include header file
#include <iostream>

using namespace std;
/*
    C++ Program for
    BST to a tree with sum of all smaller keys
*/
class TreeNode
{
	public:
	// Data value
	int data;
	// Indicates left and right subtree
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinarySearchTree
{
	public: 
    TreeNode *root;
	int sum;
	BinarySearchTree()
	{
		this->root = NULL;
		this->sum = 0;
	}
	// insert a node in BST
	void addNode(int data)
	{
		// Create new node of tree
		TreeNode *node = new TreeNode(data);
		if (this->root == NULL)
		{
			this->root = node;
		}
		else
		{
			TreeNode *auxiliary = this->root;
			// Add new node in binary search tree
			while (auxiliary != NULL)
			{
				if (data > auxiliary->data)
				{
					if (auxiliary->right == NULL)
					{
						// Add new node at right child
						auxiliary->right = node;
						return;
					}
					auxiliary = auxiliary->right;
				}
				else
				{
					if (auxiliary->left == NULL)
					{
						// Add new node at left child
						auxiliary->left = node;
						return;
					}
					auxiliary = auxiliary->left;
				}
			}
		}
	}
	// Recursive function
	// Display preorder view of binary search tree
	void preorder(TreeNode *node)
	{
		if (node != NULL)
		{
			// Print node value
			cout << " " << node->data;
			this->preorder(node->left);
			this->preorder(node->right);
		}
	}
	void replace(TreeNode *node)
	{
		if (node != NULL)
		{
			// Visit left subtree
			this->replace(node->left);
			// Add node value
			this->sum = this->sum + node->data;
			// Change node value
			node->data = this->sum;
			// Visit right subtree
			this->replace(node->right);
		}
	}
	void replaceBySmaller()
	{
		this->sum = 0;
		this->replace(this->root);
	}
};
int main()
{
	BinarySearchTree *tree = new BinarySearchTree();
	/*
	         6                            
	       /   \    
	      3     7    
	     / \     \               
	    2   4     12
	   /     \    / 
	  1       5  9
	-----------------
	    Binary Search Tree
	        
	*/
	tree->addNode(6);
	tree->addNode(3);
	tree->addNode(2);
	tree->addNode(1);
	tree->addNode(4);
	tree->addNode(5);
	tree->addNode(7);
	tree->addNode(12);
	tree->addNode(9);
	cout << "\n Before Tree Element : ";
	tree->preorder(tree->root);
	/*
	          (15+6)
	             21  
	            /   \                          
	    (1+2+3)/     \    
	          6       28  (21+7)
	         / \       \ 
	        /   \       \               
	  (1+2)3    10(6+4)  49(37+12)
	      /       \      / 
	     /         \    /
	    1          15  37
	            (10+5) (28+9)
	    -----------------
	    Resultant Binary Search Tree
	        
	*/
	tree->replaceBySmaller();
	cout << "\n After Tree Element : ";
	tree->preorder(tree->root);
	return 0;
}

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37
// Include namespace system
using System;
/*
    Csharp Program for
    BST to a tree with sum of all smaller keys
*/
public class TreeNode
{
	// Data value
	public int data;
	// Indicates left and right subtree
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinarySearchTree
{
	public TreeNode root;
	public int sum;
	public BinarySearchTree()
	{
		this.root = null;
		this.sum = 0;
	}
	// insert a node in BST
	public void addNode(int data)
	{
		// Create new node of tree
		TreeNode node = new TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			TreeNode auxiliary = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Recursive function
	// Display preorder view of binary search tree
	public void preorder(TreeNode node)
	{
		if (node != null)
		{
			// Print node value
			Console.Write(" " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	public void replace(TreeNode node)
	{
		if (node != null)
		{
			// Visit left subtree
			this.replace(node.left);
			// Add node value
			this.sum = this.sum + node.data;
			// Change node value
			node.data = this.sum;
			// Visit right subtree
			this.replace(node.right);
		}
	}
	public void replaceBySmaller()
	{
		this.sum = 0;
		this.replace(this.root);
	}
	public static void Main(String[] args)
	{
		BinarySearchTree tree = new BinarySearchTree();
		/*
		         6                            
		       /   \    
		      3     7    
		     / \     \               
		    2   4     12
		   /     \    / 
		  1       5  9
		-----------------
		    Binary Search Tree
		        
		*/
		tree.addNode(6);
		tree.addNode(3);
		tree.addNode(2);
		tree.addNode(1);
		tree.addNode(4);
		tree.addNode(5);
		tree.addNode(7);
		tree.addNode(12);
		tree.addNode(9);
		Console.Write("\n Before Tree Element : ");
		tree.preorder(tree.root);
		/*
		          (15+6)
		             21  
		            /   \                          
		    (1+2+3)/     \    
		          6       28  (21+7)
		         / \       \ 
		        /   \       \               
		  (1+2)3    10(6+4)  49(37+12)
		      /       \      / 
		     /         \    /
		    1          15  37
		            (10+5) (28+9)
		    -----------------
		    Resultant Binary Search Tree
		        
		*/
		tree.replaceBySmaller();
		Console.Write("\n After Tree Element : ");
		tree.preorder(tree.root);
	}
}

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37
package main
import "fmt"
/*
    Go Program for
    BST to a tree with sum of all smaller keys
*/
type TreeNode struct {
	// Data value
	data int
	// Indicates left and right subtree
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	var me *TreeNode = &TreeNode {}
	me.data = data
	me.left = nil
	me.right = nil
	return me
}
type BinarySearchTree struct {
	root * TreeNode
	sum int
}
func getBinarySearchTree() * BinarySearchTree {
	var me *BinarySearchTree = &BinarySearchTree {}
	me.root = nil
	me.sum = 0
	return me
}
// insert a node in BST
func(this *BinarySearchTree) addNode(data int) {
	// Create new node of tree
	var node * TreeNode = getTreeNode(data)
	if this.root == nil {
		this.root = node
	} else {
		var auxiliary * TreeNode = this.root
		// Add new node in binary search tree
		for (auxiliary != nil) {
			if data > auxiliary.data {
				if auxiliary.right == nil {
					// Add new node at right child
					auxiliary.right = node
					return
				}
				auxiliary = auxiliary.right
			} else {
				if auxiliary.left == nil {
					// Add new node at left child
					auxiliary.left = node
					return
				}
				auxiliary = auxiliary.left
			}
		}
	}
}
// Recursive function
// Display preorder view of binary search tree
func(this BinarySearchTree) preorder(node * TreeNode) {
	if node != nil {
		// Print node value
		fmt.Print(" ", node.data)
		this.preorder(node.left)
		this.preorder(node.right)
	}
}
func(this *BinarySearchTree) replace(node * TreeNode) {
	if node != nil {
		// Visit left subtree
		this.replace(node.left)
		// Add node value
		this.sum = this.sum + node.data
		// Change node value
		node.data = this.sum
		// Visit right subtree
		this.replace(node.right)
	}
}
func(this BinarySearchTree) replaceBySmaller() {
	this.sum = 0
	this.replace(this.root)
}
func main() {
	var tree * BinarySearchTree = getBinarySearchTree()
	/*
	         6                            
	       /   \    
	      3     7    
	     / \     \               
	    2   4     12
	   /     \    / 
	  1       5  9
	-----------------
	    Binary Search Tree
	        
	*/
	tree.addNode(6)
	tree.addNode(3)
	tree.addNode(2)
	tree.addNode(1)
	tree.addNode(4)
	tree.addNode(5)
	tree.addNode(7)
	tree.addNode(12)
	tree.addNode(9)
	fmt.Print("\n Before Tree Element : ")
	tree.preorder(tree.root)
	/*
	          (15+6)
	             21  
	            /   \                          
	    (1+2+3)/     \    
	          6       28  (21+7)
	         / \       \ 
	        /   \       \               
	  (1+2)3    10(6+4)  49(37+12)
	      /       \      / 
	     /         \    /
	    1          15  37
	            (10+5) (28+9)
	    -----------------
	    Resultant Binary Search Tree
	        
	*/
	tree.replaceBySmaller()
	fmt.Print("\n After Tree Element : ")
	tree.preorder(tree.root)
}

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37
<?php
/*
    Php Program for
    BST to a tree with sum of all smaller keys
*/
class TreeNode
{
	// Data value
	public $data;
	// Indicates left and right subtree
	public $left;
	public $right;
	public	function __construct($data)
	{
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinarySearchTree
{
	public $root;
	public $sum;
	public	function __construct()
	{
		$this->root = NULL;
		$this->sum = 0;
	}
	// insert a node in BST
	public	function addNode($data)
	{
		// Create new node of tree
		$node = new TreeNode($data);
		if ($this->root == NULL)
		{
			$this->root = $node;
		}
		else
		{
			$auxiliary = $this->root;
			// Add new node in binary search tree
			while ($auxiliary != NULL)
			{
				if ($data > $auxiliary->data)
				{
					if ($auxiliary->right == NULL)
					{
						// Add new node at right child
						$auxiliary->right = $node;
						return;
					}
					$auxiliary = $auxiliary->right;
				}
				else
				{
					if ($auxiliary->left == NULL)
					{
						// Add new node at left child
						$auxiliary->left = $node;
						return;
					}
					$auxiliary = $auxiliary->left;
				}
			}
		}
	}
	// Recursive function
	// Display preorder view of binary search tree
	public	function preorder($node)
	{
		if ($node != NULL)
		{
			// Print node value
			echo(" ".$node->data);
			$this->preorder($node->left);
			$this->preorder($node->right);
		}
	}
	public	function replace($node)
	{
		if ($node != NULL)
		{
			// Visit left subtree
			$this->replace($node->left);
			// Add node value
			$this->sum = $this->sum + $node->data;
			// Change node value
			$node->data = $this->sum;
			// Visit right subtree
			$this->replace($node->right);
		}
	}
	public	function replaceBySmaller()
	{
		$this->sum = 0;
		$this->replace($this->root);
	}
}

function main()
{
	$tree = new BinarySearchTree();
	/*
	         6                            
	       /   \    
	      3     7    
	     / \     \               
	    2   4     12
	   /     \    / 
	  1       5  9
	-----------------
	    Binary Search Tree
	        
	*/
	$tree->addNode(6);
	$tree->addNode(3);
	$tree->addNode(2);
	$tree->addNode(1);
	$tree->addNode(4);
	$tree->addNode(5);
	$tree->addNode(7);
	$tree->addNode(12);
	$tree->addNode(9);
	echo("\n Before Tree Element : ");
	$tree->preorder($tree->root);
	/*
	          (15+6)
	             21  
	            /   \                          
	    (1+2+3)/     \    
	          6       28  (21+7)
	         / \       \ 
	        /   \       \               
	  (1+2)3    10(6+4)  49(37+12)
	      /       \      / 
	     /         \    /
	    1          15  37
	            (10+5) (28+9)
	    -----------------
	    Resultant Binary Search Tree
	        
	*/
	$tree->replaceBySmaller();
	echo("\n After Tree Element : ");
	$tree->preorder($tree->root);
}
main();

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37
/*
    Node JS Program for
    BST to a tree with sum of all smaller keys
*/
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	constructor()
	{
		this.root = null;
		this.sum = 0;
	}
	// insert a node in BST
	addNode(data)
	{
		// Create new node of tree
		var node = new TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			var auxiliary = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Recursive function
	// Display preorder view of binary search tree
	preorder(node)
	{
		if (node != null)
		{
			// Print node value
			process.stdout.write(" " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	replace(node)
	{
		if (node != null)
		{
			// Visit left subtree
			this.replace(node.left);
			// Add node value
			this.sum = this.sum + node.data;
			// Change node value
			node.data = this.sum;
			// Visit right subtree
			this.replace(node.right);
		}
	}
	replaceBySmaller()
	{
		this.sum = 0;
		this.replace(this.root);
	}
}

function main()
{
	var tree = new BinarySearchTree();
	/*
	         6                            
	       /   \    
	      3     7    
	     / \     \               
	    2   4     12
	   /     \    / 
	  1       5  9
	-----------------
	    Binary Search Tree
	        
	*/
	tree.addNode(6);
	tree.addNode(3);
	tree.addNode(2);
	tree.addNode(1);
	tree.addNode(4);
	tree.addNode(5);
	tree.addNode(7);
	tree.addNode(12);
	tree.addNode(9);
	process.stdout.write("\n Before Tree Element : ");
	tree.preorder(tree.root);
	/*
	          (15+6)
	             21  
	            /   \                          
	    (1+2+3)/     \    
	          6       28  (21+7)
	         / \       \ 
	        /   \       \               
	  (1+2)3    10(6+4)  49(37+12)
	      /       \      / 
	     /         \    /
	    1          15  37
	            (10+5) (28+9)
	    -----------------
	    Resultant Binary Search Tree
	        
	*/
	tree.replaceBySmaller();
	process.stdout.write("\n After Tree Element : ");
	tree.preorder(tree.root);
}
main();

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37
#    Python 3 Program for
#    BST to a tree with sum of all smaller keys
class TreeNode :
	#  Data value
	#  Indicates left and right subtree
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class BinarySearchTree :
	def __init__(self) :
		self.root = None
		self.sum = 0
	
	#  insert a node in BST
	def addNode(self, data) :
		#  Create new node of tree
		node = TreeNode(data)
		if (self.root == None) :
			self.root = node
		else :
			auxiliary = self.root
			#  Add new node in binary search tree
			while (auxiliary != None) :
				if (data > auxiliary.data) :
					if (auxiliary.right == None) :
						#  Add new node at right child
						auxiliary.right = node
						return
					
					auxiliary = auxiliary.right
				else :
					if (auxiliary.left == None) :
						#  Add new node at left child
						auxiliary.left = node
						return
					
					auxiliary = auxiliary.left
				
			
		
	
	#  Recursive function
	#  Display preorder view of binary search tree
	def preorder(self, node) :
		if (node != None) :
			#  Print node value
			print(" ", node.data, end = "")
			self.preorder(node.left)
			self.preorder(node.right)
		
	
	def replace(self, node) :
		if (node != None) :
			#  Visit left subtree
			self.replace(node.left)
			#  Add node value
			self.sum = self.sum + node.data
			#  Change node value
			node.data = self.sum
			#  Visit right subtree
			self.replace(node.right)
		
	
	def replaceBySmaller(self) :
		self.sum = 0
		self.replace(self.root)
	

def main() :
	tree = BinarySearchTree()
	#         6                            
	#       /   \    
	#      3     7    
	#     / \     \               
	#    2   4     12
	#   /     \    / 
	#  1       5  9
	# -----------------
	#    Binary Search Tree
	tree.addNode(6)
	tree.addNode(3)
	tree.addNode(2)
	tree.addNode(1)
	tree.addNode(4)
	tree.addNode(5)
	tree.addNode(7)
	tree.addNode(12)
	tree.addNode(9)
	print("\n Before Tree Element : ", end = "")
	tree.preorder(tree.root)
	#          (15+6)
	#             21  
	#            /   \                          
	#    (1+2+3)/     \    
	#          6       28  (21+7)
	#         / \       \ 
	#        /   \       \               
	#  (1+2)3    10(6+4)  49(37+12)
	#      /       \      / 
	#     /         \    /
	#    1          15  37
	#            (10+5) (28+9)
	#    -----------------
	#    Resultant Binary Search Tree
	tree.replaceBySmaller()
	print("\n After Tree Element : ", end = "")
	tree.preorder(tree.root)

if __name__ == "__main__": main()

Output

 Before Tree Element :   6  3  2  1  4  5  7  12  9
 After Tree Element :   21  6  3  1  10  15  28  49  37
#    Ruby Program for
#    BST to a tree with sum of all smaller keys
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	#  Data value
	#  Indicates left and right subtree
	def initialize(data) 
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinarySearchTree 
	# Define the accessor and reader of class BinarySearchTree
	attr_reader :root, :sum
	attr_accessor :root, :sum
	def initialize() 
		self.root = nil
		self.sum = 0
	end

	#  insert a node in BST
	def addNode(data) 
		#  Create new node of tree
		node = TreeNode.new(data)
		if (self.root == nil) 
			self.root = node
		else
 
			auxiliary = self.root
			#  Add new node in binary search tree
			while (auxiliary != nil) 
				if (data > auxiliary.data) 
					if (auxiliary.right == nil) 
						#  Add new node at right child
						auxiliary.right = node
						return
					end

					auxiliary = auxiliary.right
				else
 
					if (auxiliary.left == nil) 
						#  Add new node at left child
						auxiliary.left = node
						return
					end

					auxiliary = auxiliary.left
				end

			end

		end

	end

	#  Recursive function
	#  Display preorder view of binary search tree
	def preorder(node) 
		if (node != nil) 
			#  Print node value
			print(" ", node.data)
			self.preorder(node.left)
			self.preorder(node.right)
		end

	end

	def replace(node) 
		if (node != nil) 
			#  Visit left subtree
			self.replace(node.left)
			#  Add node value
			self.sum = self.sum + node.data
			#  Change node value
			node.data = self.sum
			#  Visit right subtree
			self.replace(node.right)
		end

	end

	def replaceBySmaller() 
		self.sum = 0
		self.replace(self.root)
	end

end

def main() 
	tree = BinarySearchTree.new()
	#         6                            
	#       /   \    
	#      3     7    
	#     / \     \               
	#    2   4     12
	#   /     \    / 
	#  1       5  9
	# -----------------
	#    Binary Search Tree
	tree.addNode(6)
	tree.addNode(3)
	tree.addNode(2)
	tree.addNode(1)
	tree.addNode(4)
	tree.addNode(5)
	tree.addNode(7)
	tree.addNode(12)
	tree.addNode(9)
	print("\n Before Tree Element : ")
	tree.preorder(tree.root)
	#          (15+6)
	#             21  
	#            /   \                          
	#    (1+2+3)/     \    
	#          6       28  (21+7)
	#         / \       \ 
	#        /   \       \               
	#  (1+2)3    10(6+4)  49(37+12)
	#      /       \      / 
	#     /         \    /
	#    1          15  37
	#            (10+5) (28+9)
	#    -----------------
	#    Resultant Binary Search Tree
	tree.replaceBySmaller()
	print("\n After Tree Element : ")
	tree.preorder(tree.root)
end

main()

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37
/*
    Scala Program for
    BST to a tree with sum of all smaller keys
*/
class TreeNode(
	// Data value
	var data: Int,
		// Indicates left and right subtree
		var left: TreeNode,
			var right: TreeNode)
{
	def this(data: Int)
	{
		this(data,null,null);
	}
}
class BinarySearchTree(var root: TreeNode,
	var sum: Int)
{
	def this()
	{
		this(null,0);
	}
	// insert a node in BST
	def addNode(data: Int): Unit = {
		// Create new node of tree
		var node: TreeNode = new TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			var auxiliary: TreeNode = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Recursive function
	// Display preorder view of binary search tree
	def preorder(node: TreeNode): Unit = {
		if (node != null)
		{
			// Print node value
			print(" " + node.data);
			preorder(node.left);
			preorder(node.right);
		}
	}
	def replace(node: TreeNode): Unit = {
		if (node != null)
		{
			// Visit left subtree
			replace(node.left);
			// Add node value
			this.sum = this.sum + node.data;
			// Change node value
			node.data = this.sum;
			// Visit right subtree
			replace(node.right);
		}
	}
	def replaceBySmaller(): Unit = {
		this.sum = 0;
		this.replace(this.root);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinarySearchTree = new BinarySearchTree();
		/*
		         6                            
		       /   \    
		      3     7    
		     / \     \               
		    2   4     12
		   /     \    / 
		  1       5  9
		-----------------
		    Binary Search Tree
		        
		*/
		tree.addNode(6);
		tree.addNode(3);
		tree.addNode(2);
		tree.addNode(1);
		tree.addNode(4);
		tree.addNode(5);
		tree.addNode(7);
		tree.addNode(12);
		tree.addNode(9);
		print("\n Before Tree Element : ");
		tree.preorder(tree.root);
		/*
		          (15+6)
		             21  
		            /   \                          
		    (1+2+3)/     \    
		          6       28  (21+7)
		         / \       \ 
		        /   \       \               
		  (1+2)3    10(6+4)  49(37+12)
		      /       \      / 
		     /         \    /
		    1          15  37
		            (10+5) (28+9)
		    -----------------
		    Resultant Binary Search Tree
		        
		*/
		tree.replaceBySmaller();
		print("\n After Tree Element : ");
		tree.preorder(tree.root);
	}
}

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37
/*
    Swift 4 Program for
    BST to a tree with sum of all smaller keys
*/
class TreeNode
{
	// Data value
	var data: Int;
	// Indicates left and right subtree
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinarySearchTree
{
	var root: TreeNode? ;
	var sum: Int;
	init()
	{
		self.root = nil;
		self.sum = 0;
	}
	// insert a node in BST
	func addNode(_ data: Int)
	{
		// Create new node of tree
		let node: TreeNode = TreeNode(data);
		if (self.root == nil)
		{
			self.root = node;
		}
		else
		{
			var auxiliary: TreeNode? = self.root;
			// Add new node in binary search tree
			while (auxiliary  != nil)
			{
				if (data > auxiliary!.data)
				{
					if (auxiliary!.right == nil)
					{
						// Add new node at right child
						auxiliary!.right = node;
						return;
					}
					auxiliary = auxiliary!.right;
				}
				else
				{
					if (auxiliary!.left == nil)
					{
						// Add new node at left child
						auxiliary!.left = node;
						return;
					}
					auxiliary = auxiliary!.left;
				}
			}
		}
	}
	// Recursive function
	// Display preorder view of binary search tree
	func preorder(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			// Print node value
			print(" ", node!.data, terminator: "");
			self.preorder(node!.left);
			self.preorder(node!.right);
		}
	}
	func replace(_ node: TreeNode? )
	{
		if (node  != nil)
		{
			// Visit left subtree
			self.replace(node!.left);
			// Add node value
			self.sum = self.sum + node!.data;
			// Change node value
			node!.data = self.sum;
			// Visit right subtree
			self.replace(node!.right);
		}
	}
	func replaceBySmaller()
	{
		self.sum = 0;
		self.replace(self.root);
	}
}
func main()
{
	let tree: BinarySearchTree = BinarySearchTree();
	/*
	         6                            
	       /   \    
	      3     7    
	     / \     \               
	    2   4     12
	   /     \    / 
	  1       5  9
	-----------------
	    Binary Search Tree
	        
	*/
	tree.addNode(6);
	tree.addNode(3);
	tree.addNode(2);
	tree.addNode(1);
	tree.addNode(4);
	tree.addNode(5);
	tree.addNode(7);
	tree.addNode(12);
	tree.addNode(9);
	print("\n Before Tree Element : ", terminator: "");
	tree.preorder(tree.root);
	/*
	          (15+6)
	             21  
	            /   \                          
	    (1+2+3)/     \    
	          6       28  (21+7)
	         / \       \ 
	        /   \       \               
	  (1+2)3    10(6+4)  49(37+12)
	      /       \      / 
	     /         \    /
	    1          15  37
	            (10+5) (28+9)
	    -----------------
	    Resultant Binary Search Tree
	        
	*/
	tree.replaceBySmaller();
	print("\n After Tree Element : ", terminator: "");
	tree.preorder(tree.root);
}
main();

Output

 Before Tree Element :   6  3  2  1  4  5  7  12  9
 After Tree Element :   21  6  3  1  10  15  28  49  37
/*
    Kotlin Program for
    BST to a tree with sum of all smaller keys
*/
class TreeNode
{
	// Data value
	var data: Int;
	// Indicates left and right subtree
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinarySearchTree
{
	var root: TreeNode ? ;
	var sum: Int;
	constructor()
	{
		this.root = null;
		this.sum = 0;
	}
	// insert a node in BST
	fun addNode(data: Int): Unit
	{
		// Create new node of tree
		val node: TreeNode = TreeNode(data);
		if (this.root == null)
		{
			this.root = node;
		}
		else
		{
			var auxiliary: TreeNode ? = this.root;
			// Add new node in binary search tree
			while (auxiliary != null)
			{
				if (data > auxiliary.data)
				{
					if (auxiliary.right == null)
					{
						// Add new node at right child
						auxiliary.right = node;
						return;
					}
					auxiliary = auxiliary.right;
				}
				else
				{
					if (auxiliary.left == null)
					{
						// Add new node at left child
						auxiliary.left = node;
						return;
					}
					auxiliary = auxiliary.left;
				}
			}
		}
	}
	// Recursive function
	// Display preorder view of binary search tree
	fun preorder(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Print node value
			print(" " + node.data);
			this.preorder(node.left);
			this.preorder(node.right);
		}
	}
	fun replace(node: TreeNode ? ): Unit
	{
		if (node != null)
		{
			// Visit left subtree
			this.replace(node.left);
			// Add node value
			this.sum = this.sum + node.data;
			// Change node value
			node.data = this.sum;
			// Visit right subtree
			this.replace(node.right);
		}
	}
	fun replaceBySmaller(): Unit
	{
		this.sum = 0;
		this.replace(this.root);
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinarySearchTree = BinarySearchTree();
	/*
	         6                            
	       /   \    
	      3     7    
	     / \     \               
	    2   4     12
	   /     \    / 
	  1       5  9
	-----------------
	    Binary Search Tree
	        
	*/
	tree.addNode(6);
	tree.addNode(3);
	tree.addNode(2);
	tree.addNode(1);
	tree.addNode(4);
	tree.addNode(5);
	tree.addNode(7);
	tree.addNode(12);
	tree.addNode(9);
	print("\n Before Tree Element : ");
	tree.preorder(tree.root);
	/*
	          (15+6)
	             21  
	            /   \                          
	    (1+2+3)/     \    
	          6       28  (21+7)
	         / \       \ 
	        /   \       \               
	  (1+2)3    10(6+4)  49(37+12)
	      /       \      / 
	     /         \    /
	    1          15  37
	            (10+5) (28+9)
	    -----------------
	    Resultant Binary Search Tree
	        
	*/
	tree.replaceBySmaller();
	print("\n After Tree Element : ");
	tree.preorder(tree.root);
}

Output

 Before Tree Element :  6 3 2 1 4 5 7 12 9
 After Tree Element :  21 6 3 1 10 15 28 49 37


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