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 37package 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