Max average of subtree values in a given binary tree

Here given code implementation process.
// C program for
// Max average of subtree values in a given binary tree
#include <stdio.h>
#include <stdlib.h>
// Tree Node
struct TreeNode
{
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// Binary Tree
struct BinaryTree
{
struct TreeNode *root;
};
// Create new tree
struct BinaryTree *newTree()
{
// Create dynamic node
struct BinaryTree *tree =
(struct BinaryTree *) malloc(sizeof(struct BinaryTree));
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 tree node
struct TreeNode *newNode(int data)
{
// Create dynamic node
struct TreeNode *new_node =
(struct TreeNode *) malloc(sizeof(struct TreeNode));
if (new_node != NULL)
{
//Set data and pointer values
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
}
else
{
//This is indicates, segmentation fault or memory overflow problem
printf("Memory Overflow\n");
}
//return new node
return new_node;
}
double maxValue(double a, double b)
{
if (a > b)
{
return a;
}
return b;
}
int findMaxAverage(struct TreeNode *node, double *average, int *count)
{
if (node == NULL)
{
return 0;
}
int leftSubTree = 0;
int rightSubTree = 0;
// Sum of left and right sub tree
int lSum = findMaxAverage(node->left, average, & leftSubTree);
int rSum = findMaxAverage(node->right, average, & rightSubTree);
// Calculate sum of subtree nodes
int sum = lSum + rSum + node->data;
*count = leftSubTree + rightSubTree + 1;
// Display calculated operation
printf("\n Node : %d + [left subtree sum : %d + right subtree sum : %d ] ",
node->data, lSum, rSum);
printf("\n Total Node : %d ", *count);
printf("\n Average : (%d/%d) = %lf \n",
sum, *count , (double) sum / *count);
if ( *count == 0)
{
*average = maxValue( *average, (double) sum);
}
else
{
*average = maxValue( *average, (double) sum / *count);
}
return sum;
}
// Handles the request to find average of max subtree
void maxAverage(struct TreeNode *root)
{
if (root == NULL)
{
return;
}
double average = 0.0;
int count = 0;
findMaxAverage(root, & average, & count);
// Display final result
printf("\n Result : %lf ", average);
}
int main(int argc, char
const *argv[])
{
struct BinaryTree *tree = newTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree->root = newNode(4);
tree->root->left = newNode(-4);
tree->root->right = newNode(7);
tree->root->right->right = newNode(12);
tree->root->right->right->left = newNode(15);
tree->root->left->right = newNode(30);
tree->root->left->right->right = newNode(18);
tree->root->left->right->left = newNode(15);
tree->root->left->left = newNode(2);
tree->root->left->left->left = newNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
maxAverage(tree->root);
return 0;
}
Output
Node : 19 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19.000000
Node : 2 + [left subtree sum : 19 + right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.500000
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.000000
Node : 18 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18.000000
Node : 30 + [left subtree sum : 15 + right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21.000000
Node : -4 + [left subtree sum : 21 + right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.333333
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.000000
Node : 12 + [left subtree sum : 15 + right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.500000
Node : 7 + [left subtree sum : 0 + right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.333333
Node : 4 + [left subtree sum : 80 + right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.800000
Result : 21.000000
/*
Java program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public int count;
public double average;
public BinaryTree()
{
// Set initial value
this.root = null;
this.count = 0;
this.average = 0.0;
}
public double maxValue(double a, double b)
{
if (a > b)
{
return a;
}
return b;
}
public int findMaxAverage(TreeNode node)
{
if (node == null)
{
return 0;
}
int back = this.count;
this.count++;
// Sum of left and right sub tree
int lSum = findMaxAverage(node.left);
int rSum = findMaxAverage(node.right);
// Calculate sum of subtree nodes
int sum = lSum + rSum + node.data;
int totalNode = this.count - back;
// Display calculated operation
System.out.print("\n Node : " +
node.data + " + [left subtree sum : " +
lSum + " + right subtree sum : " + rSum + " ] ");
System.out.print("\n Total Node : " + totalNode);
System.out.print("\n Average : (" +
sum + "/" + totalNode + ") = " +
((double) sum / totalNode) + " \n");
if (totalNode == 0)
{
this.average = maxValue(average, (double) sum);
}
else
{
this.average = maxValue(average, (double) sum / totalNode);
}
return sum;
}
// Handles the request to find average of max subtree
public void maxAverage()
{
if (this.root == null)
{
return;
}
this.average = -Double.MAX_VALUE;
this.count = 0;
this.findMaxAverage(this.root);
// Display final result
System.out.print("\n Result : " + this.average);
}
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(-4);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.left = new TreeNode(15);
tree.root.left.right = new TreeNode(30);
tree.root.left.right.right = new TreeNode(18);
tree.root.left.right.left = new TreeNode(15);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
tree.maxAverage();
}
}
Output
Node : 19 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19.0
Node : 2 + [left subtree sum : 19 + right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.0
Node : 18 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18.0
Node : 30 + [left subtree sum : 15 + right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21.0
Node : -4 + [left subtree sum : 21 + right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.333333333333334
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.0
Node : 12 + [left subtree sum : 15 + right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7 + [left subtree sum : 0 + right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.333333333333334
Node : 4 + [left subtree sum : 80 + right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21.0
// Include header file
#include <iostream>
#include <float.h>
using namespace std;
/*
C++ program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public:
TreeNode *root;
int count;
double average;
BinaryTree()
{
this->root = NULL;
this->count = 0;
this->average = 0.0;
}
double maxValue(double a, double b)
{
if (a > b)
{
return a;
}
return b;
}
int findMaxAverage(TreeNode *node)
{
if (node == NULL)
{
return 0;
}
int back = this->count;
this->count++;
// Sum of left and right sub tree
int lSum = this->findMaxAverage(node->left);
int rSum = this->findMaxAverage(node->right);
// Calculate sum of subtree nodes
int sum = lSum + rSum + node->data;
int totalNode = this->count - back;
// Display calculated operation
cout << "\n Node : "
<< node->data << " + [left subtree sum : "
<< lSum << " + right subtree sum : " << rSum << " ] ";
cout << "\n Total Node : " << totalNode;
cout << "\n Average : ("
<< sum << "/" << totalNode << ") = "
<< ((double) sum / totalNode) << " \n";
if (totalNode == 0)
{
this->average = this->maxValue(this->average, (double) sum);
}
else
{
this->average = this->maxValue
(
this->average, (double) sum / totalNode
);
}
return sum;
}
// Handles the request to find average of max subtree
void maxAverage()
{
if (this->root == NULL)
{
return;
}
this->average = -DBL_MAX;
this->count = 0;
this->findMaxAverage(this->root);
// Display final result
cout << "\n Result : " << this->average;
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree->root = new TreeNode(4);
tree->root->left = new TreeNode(-4);
tree->root->right = new TreeNode(7);
tree->root->right->right = new TreeNode(12);
tree->root->right->right->left = new TreeNode(15);
tree->root->left->right = new TreeNode(30);
tree->root->left->right->right = new TreeNode(18);
tree->root->left->right->left = new TreeNode(15);
tree->root->left->left = new TreeNode(2);
tree->root->left->left->left = new TreeNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
tree->maxAverage();
return 0;
}
Output
Node : 19 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19
Node : 2 + [left subtree sum : 19 + right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 18 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18
Node : 30 + [left subtree sum : 15 + right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21
Node : -4 + [left subtree sum : 21 + right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.3333
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 12 + [left subtree sum : 15 + right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7 + [left subtree sum : 0 + right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.3333
Node : 4 + [left subtree sum : 80 + right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21
// Include namespace system
using System;
/*
Csharp program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public int count;
public double average;
public BinaryTree()
{
// Set initial value
this.root = null;
this.count = 0;
this.average = 0.0;
}
public double maxValue(double a, double b)
{
if (a > b)
{
return a;
}
return b;
}
public int findMaxAverage(TreeNode node)
{
if (node == null)
{
return 0;
}
int back = this.count;
this.count++;
// Sum of left and right sub tree
int lSum = this.findMaxAverage(node.left);
int rSum = this.findMaxAverage(node.right);
// Calculate sum of subtree nodes
int sum = lSum + rSum + node.data;
int totalNode = this.count - back;
// Display calculated operation
Console.Write("\n Node : " + node.data +
" + [left subtree sum : " + lSum +
" + right subtree sum : " + rSum + " ] ");
Console.Write("\n Total Node : " + totalNode);
Console.Write("\n Average : (" +
sum + "/" + totalNode + ") = " +
((double) sum / totalNode) + " \n");
if (totalNode == 0)
{
this.average = this.maxValue(
this.average, (double) sum
);
}
else
{
this.average = this.maxValue(
this.average, (double) sum / totalNode
);
}
return sum;
}
// Handles the request to find average of max subtree
public void maxAverage()
{
if (this.root == null)
{
return;
}
this.average = -double.MaxValue;
this.count = 0;
this.findMaxAverage(this.root);
// Display final result
Console.Write("\n Result : " + this.average);
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(-4);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.left = new TreeNode(15);
tree.root.left.right = new TreeNode(30);
tree.root.left.right.right = new TreeNode(18);
tree.root.left.right.left = new TreeNode(15);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
tree.maxAverage();
}
}
Output
Node : 19 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19
Node : 2 + [left subtree sum : 19 + right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 18 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18
Node : 30 + [left subtree sum : 15 + right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21
Node : -4 + [left subtree sum : 21 + right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.3333333333333
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 12 + [left subtree sum : 15 + right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7 + [left subtree sum : 0 + right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.3333333333333
Node : 4 + [left subtree sum : 80 + right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21
<?php
/*
Php program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree
{
public $root;
public $count;
public $average;
public function __construct()
{
$this->root = NULL;
$this->count = 0;
$this->average = 0.0;
}
public function maxValue($a, $b)
{
if ($a > $b)
{
return $a;
}
return $b;
}
public function findMaxAverage($node)
{
if ($node == NULL)
{
return 0;
}
$back = $this->count;
$this->count++;
// Sum of left and right sub tree
$lSum = $this->findMaxAverage($node->left);
$rSum = $this->findMaxAverage($node->right);
// Calculate sum of subtree nodes
$sum = $lSum + $rSum + $node->data;
$totalNode = $this->count - $back;
// Display calculated operation
echo("\n Node : ".$node->data.
". [left subtree sum : ".$lSum.
". right subtree sum : ".$rSum.
" ] ");
echo("\n Total Node : ".$totalNode);
echo("\n Average : (".$sum.
"/".$totalNode.
") = ".((double) $sum / $totalNode).
" \n");
if ($totalNode == 0)
{
$this->average = $this->maxValue($this->average, (double) $sum);
}
else
{
$this->average = $this->maxValue($this->average, (double) $sum / $totalNode);
}
return $sum;
}
// Handles the request to find average of max subtree
public function maxAverage()
{
if ($this->root == NULL)
{
return;
}
$this->average = -PHP_INT_MAX;
$this->count = 0;
$this->findMaxAverage($this->root);
// Display final result
echo("\n Result : ".$this->average);
}
}
function main()
{
$tree = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
$tree->root = new TreeNode(4);
$tree->root->left = new TreeNode(-4);
$tree->root->right = new TreeNode(7);
$tree->root->right->right = new TreeNode(12);
$tree->root->right->right->left = new TreeNode(15);
$tree->root->left->right = new TreeNode(30);
$tree->root->left->right->right = new TreeNode(18);
$tree->root->left->right->left = new TreeNode(15);
$tree->root->left->left = new TreeNode(2);
$tree->root->left->left->left = new TreeNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
$tree->maxAverage();
}
main();
Output
Node : 19. [left subtree sum : 0. right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19
Node : 2. [left subtree sum : 19. right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15. [left subtree sum : 0. right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 18. [left subtree sum : 0. right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18
Node : 30. [left subtree sum : 15. right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21
Node : -4. [left subtree sum : 21. right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.333333333333
Node : 15. [left subtree sum : 0. right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 12. [left subtree sum : 15. right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7. [left subtree sum : 0. right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.333333333333
Node : 4. [left subtree sum : 80. right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21
package main
import "fmt"
import "math"
/*
Go program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
me.data = data
me.left = nil
me.right = nil
return me
}
type BinaryTree struct {
root * TreeNode
count int
average float64
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
// Set initial value
me.root = nil
me.count = 0
me.average = 0.0
return me
}
func(this BinaryTree) maxValue(a, b float64) float64 {
if a > b {
return a
}
return b
}
func(this *BinaryTree) findMaxAverage(node * TreeNode) int {
if node == nil {
return 0
}
var back int = this.count
this.count++
// Sum of left and right sub tree
var lSum int = this.findMaxAverage(node.left)
var rSum int = this.findMaxAverage(node.right)
// Calculate sum of subtree nodes
var sum int = lSum + rSum + node.data
var totalNode int = this.count - back
// Display calculated operation
fmt.Print("\n Node : ", node.data, " + [left subtree sum : ", lSum, " + right subtree sum : ", rSum, " ] ")
fmt.Print("\n Total Node : ", totalNode)
fmt.Print("\n Average : (", sum, "/", totalNode, ") = ", float64(sum) / float64(totalNode), " \n")
if totalNode == 0 {
this.average = this.maxValue(this.average, float64(sum))
} else {
this.average = this.maxValue(this.average,float64(sum) / float64(totalNode))
}
return sum
}
// Handles the request to find average of max subtree
func(this BinaryTree) maxAverage() {
if this.root == nil {
return
}
this.average = -math.MaxFloat64
this.count = 0
this.findMaxAverage(this.root)
// Display final result
fmt.Print("\n Result : ", this.average)
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree.root = getTreeNode(4)
tree.root.left = getTreeNode(-4)
tree.root.right = getTreeNode(7)
tree.root.right.right = getTreeNode(12)
tree.root.right.right.left = getTreeNode(15)
tree.root.left.right = getTreeNode(30)
tree.root.left.right.right = getTreeNode(18)
tree.root.left.right.left = getTreeNode(15)
tree.root.left.left = getTreeNode(2)
tree.root.left.left.left = getTreeNode(19)
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
tree.maxAverage()
}
Output
Node : 19 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19
Node : 2 + [left subtree sum : 19 + right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 18 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18
Node : 30 + [left subtree sum : 15 + right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21
Node : -4 + [left subtree sum : 21 + right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.333333333333334
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 12 + [left subtree sum : 15 + right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7 + [left subtree sum : 0 + right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.333333333333334
Node : 4 + [left subtree sum : 80 + right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21
/*
Node JS program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
this.count = 0;
this.average = 0.0;
}
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
findMaxAverage(node)
{
if (node == null)
{
return 0;
}
var back = this.count;
this.count++;
// Sum of left and right sub tree
var lSum = this.findMaxAverage(node.left);
var rSum = this.findMaxAverage(node.right);
// Calculate sum of subtree nodes
var sum = lSum + rSum + node.data;
var totalNode = this.count - back;
// Display calculated operation
process.stdout.write("\n Node : " +
node.data + " + [left subtree sum : " +
lSum + " + right subtree sum : " + rSum + " ] ");
process.stdout.write("\n Total Node : " + totalNode);
process.stdout.write("\n Average : (" +
sum + "/" + totalNode + ") = " +
(sum / totalNode) + " \n");
if (totalNode == 0)
{
this.average = this.maxValue(
this.average, sum
);
}
else
{
this.average = this.maxValue(
this.average, sum / totalNode
);
}
return sum;
}
// Handles the request to find average of max subtree
maxAverage()
{
if (this.root == null)
{
return;
}
this.average = -Number.MAX_VALUE;
this.count = 0;
this.findMaxAverage(this.root);
// Display final result
process.stdout.write("\n Result : " + this.average);
}
}
function main()
{
var tree = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(-4);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.left = new TreeNode(15);
tree.root.left.right = new TreeNode(30);
tree.root.left.right.right = new TreeNode(18);
tree.root.left.right.left = new TreeNode(15);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
tree.maxAverage();
}
main();
Output
Node : 19 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19
Node : 2 + [left subtree sum : 19 + right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 18 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18
Node : 30 + [left subtree sum : 15 + right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21
Node : -4 + [left subtree sum : 21 + right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.333333333333334
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15
Node : 12 + [left subtree sum : 15 + right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7 + [left subtree sum : 0 + right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.333333333333334
Node : 4 + [left subtree sum : 80 + right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21
import sys
# Python 3 program for
# Find the minimum leaf node in a binary tree
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
self.count = 0
self.average = 0.0
def maxValue(self, a, b) :
if (a > b) :
return a
return b
def findMaxAverage(self, node) :
if (node == None) :
return 0
back = self.count
self.count += 1
# Sum of left and right sub tree
lSum = self.findMaxAverage(node.left)
rSum = self.findMaxAverage(node.right)
# Calculate sum of subtree nodes
sum = lSum + rSum + node.data
totalNode = self.count - back
# Display calculated operation
print("\n Node : ", node.data ,
", [left subtree sum : ", lSum ,
", right subtree sum : ", rSum ," ] ", end = "")
print("\n Total Node : ", totalNode, end = "")
print("\n Average : (", sum ,"/", totalNode , ") = ",
(sum / totalNode) ," ")
if (totalNode == 0) :
self.average = self.maxValue(
self.average, sum
)
else :
self.average = self.maxValue(
self.average, sum / totalNode
)
return sum
# Handles the request to find average of max subtree
def maxAverage(self) :
if (self.root == None) :
return
self.average = -sys.maxsize
self.count = 0
self.findMaxAverage(self.root)
# Display final result
print("\n Result : ", self.average, end = "")
def main() :
tree = BinaryTree()
# 4
# / \
# -4 7
# / \ \
# 2 30 12
# / / \ /
# 19 15 18 15
# -----------------
# Binary tree
tree.root = TreeNode(4)
tree.root.left = TreeNode(-4)
tree.root.right = TreeNode(7)
tree.root.right.right = TreeNode(12)
tree.root.right.right.left = TreeNode(15)
tree.root.left.right = TreeNode(30)
tree.root.left.right.right = TreeNode(18)
tree.root.left.right.left = TreeNode(15)
tree.root.left.left = TreeNode(2)
tree.root.left.left.left = TreeNode(19)
# Max subtree
# [30+15+18] / 3 = (63 /3 ) = 21
# Here 3 indicates number of nodes
tree.maxAverage()
if __name__ == "__main__": main()
Output
Node : 19 , [left subtree sum : 0 , right subtree sum : 0 ]
Total Node : 1
Average : ( 19 / 1 ) = 19.0
Node : 2 , [left subtree sum : 19 , right subtree sum : 0 ]
Total Node : 2
Average : ( 21 / 2 ) = 10.5
Node : 15 , [left subtree sum : 0 , right subtree sum : 0 ]
Total Node : 1
Average : ( 15 / 1 ) = 15.0
Node : 18 , [left subtree sum : 0 , right subtree sum : 0 ]
Total Node : 1
Average : ( 18 / 1 ) = 18.0
Node : 30 , [left subtree sum : 15 , right subtree sum : 18 ]
Total Node : 3
Average : ( 63 / 3 ) = 21.0
Node : -4 , [left subtree sum : 21 , right subtree sum : 63 ]
Total Node : 6
Average : ( 80 / 6 ) = 13.333333333333334
Node : 15 , [left subtree sum : 0 , right subtree sum : 0 ]
Total Node : 1
Average : ( 15 / 1 ) = 15.0
Node : 12 , [left subtree sum : 15 , right subtree sum : 0 ]
Total Node : 2
Average : ( 27 / 2 ) = 13.5
Node : 7 , [left subtree sum : 0 , right subtree sum : 27 ]
Total Node : 3
Average : ( 34 / 3 ) = 11.333333333333334
Node : 4 , [left subtree sum : 80 , right subtree sum : 34 ]
Total Node : 10
Average : ( 118 / 10 ) = 11.8
Result : 21.0
# Ruby program for
# Find the minimum leaf node in a binary tree
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
self.data = data
self.left = nil
self.right = nil
end
end
class BinaryTree
# Define the accessor and reader of class BinaryTree
attr_reader :root, :count, :average
attr_accessor :root, :count, :average
def initialize()
self.root = nil
self.count = 0
self.average = 0.0
end
def maxValue(a, b)
if (a > b)
return a
end
return b
end
def findMaxAverage(node)
if (node == nil)
return 0
end
back = self.count
self.count += 1
# Sum of left and right sub tree
lSum = self.findMaxAverage(node.left)
rSum = self.findMaxAverage(node.right)
# Calculate sum of subtree nodes
sum = lSum + rSum + node.data
totalNode = self.count - back
# Display calculated operation
print("\n Node : ", node.data ,
", [left subtree sum : ", lSum ,
", right subtree sum : ", rSum ," ] ")
print("\n Total Node : ", totalNode)
print("\n Average : (",
sum ,"/", totalNode ,") = ",
( sum.to_f / totalNode) ," \n")
if (totalNode == 0)
self.average = self.maxValue(
self.average, sum.to_f
)
else
self.average = self.maxValue(
self.average, sum.to_f / totalNode
)
end
return sum
end
# Handles the request to find average of max subtree
def maxAverage()
if (self.root == nil)
return
end
self.average = -(2**(0.size*8-2))
self.count = 0
self.findMaxAverage(self.root)
# Display final result
print("\n Result : ", self.average)
end
end
def main()
tree = BinaryTree.new()
# 4
# / \
# -4 7
# / \ \
# 2 30 12
# / / \ /
# 19 15 18 15
# -----------------
# Binary tree
tree.root = TreeNode.new(4)
tree.root.left = TreeNode.new(-4)
tree.root.right = TreeNode.new(7)
tree.root.right.right = TreeNode.new(12)
tree.root.right.right.left = TreeNode.new(15)
tree.root.left.right = TreeNode.new(30)
tree.root.left.right.right = TreeNode.new(18)
tree.root.left.right.left = TreeNode.new(15)
tree.root.left.left = TreeNode.new(2)
tree.root.left.left.left = TreeNode.new(19)
# Max subtree
# [30+15+18] / 3 = (63 /3 ) = 21
# Here 3 indicates number of nodes
tree.maxAverage()
end
main()
Output
Node : 19, [left subtree sum : 0, right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19.0
Node : 2, [left subtree sum : 19, right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15, [left subtree sum : 0, right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.0
Node : 18, [left subtree sum : 0, right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18.0
Node : 30, [left subtree sum : 15, right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21.0
Node : -4, [left subtree sum : 21, right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.333333333333334
Node : 15, [left subtree sum : 0, right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.0
Node : 12, [left subtree sum : 15, right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7, [left subtree sum : 0, right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.333333333333334
Node : 4, [left subtree sum : 80, right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21.0
/*
Scala program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null, null);
}
}
class BinaryTree(var root: TreeNode,
var count: Int,
var average: Double)
{
def this()
{
this( null,0,0.0);
}
def maxValue(a: Double, b: Double): Double = {
if (a > b)
{
return a;
}
return b;
}
def findMaxAverage(node: TreeNode): Int = {
if (node == null)
{
return 0;
}
var back: Int = this.count;
this.count += 1;
// Sum of left and right sub tree
var lSum: Int = findMaxAverage(node.left);
var rSum: Int = findMaxAverage(node.right);
// Calculate sum of subtree nodes
var sum: Int = lSum + rSum + node.data;
var totalNode: Int = this.count - back;
// Display calculated operation
print("\n Node : " + node.data +
" + [left subtree sum : " + lSum +
" + right subtree sum : " + rSum + " ] ");
print("\n Total Node : " + totalNode);
print("\n Average : (" +
sum + "/" + totalNode + ") = " +
(sum.toDouble / totalNode) + " \n");
if (totalNode == 0)
{
this.average = maxValue(average, sum.toDouble);
}
else
{
this.average = maxValue(average, sum.toDouble / totalNode);
}
return sum;
}
// Handles the request to find average of max subtree
def maxAverage(): Unit = {
if (this.root == null)
{
return;
}
this.average = Double.NegativeInfinity;
this.count = 0;
this.findMaxAverage(this.root);
// Display final result
print("\n Result : " + this.average);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(-4);
tree.root.right = new TreeNode(7);
tree.root.right.right = new TreeNode(12);
tree.root.right.right.left = new TreeNode(15);
tree.root.left.right = new TreeNode(30);
tree.root.left.right.right = new TreeNode(18);
tree.root.left.right.left = new TreeNode(15);
tree.root.left.left = new TreeNode(2);
tree.root.left.left.left = new TreeNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
tree.maxAverage();
}
}
Output
Node : 19 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19.0
Node : 2 + [left subtree sum : 19 + right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.0
Node : 18 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18.0
Node : 30 + [left subtree sum : 15 + right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21.0
Node : -4 + [left subtree sum : 21 + right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.333333333333334
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.0
Node : 12 + [left subtree sum : 15 + right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7 + [left subtree sum : 0 + right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.333333333333334
Node : 4 + [left subtree sum : 80 + right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21.0
/*
Swift 4 program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
var count: Int;
var average: Double;
init()
{
self.root = nil;
self.count = 0;
self.average = 0.0;
}
func maxValue(_ a: Double, _ b: Double) -> Double
{
if (a > b)
{
return a;
}
return b;
}
func findMaxAverage(_ node: TreeNode? ) -> Int
{
if (node == nil)
{
return 0;
}
let back: Int = self.count;
self.count += 1;
// Sum of left and right sub tree
let lSum: Int = self.findMaxAverage(node!.left);
let rSum: Int = self.findMaxAverage(node!.right);
// Calculate sum of subtree nodes
let sum: Int = lSum + rSum + node!.data;
let totalNode: Int = self.count - back;
// Display calculated operation
print("\n Node : ", node!.data ,
", [left subtree sum : ",
lSum ,", right subtree sum : ",
rSum ," ] ", terminator: "");
print("\n Total Node : ", totalNode, terminator: "");
print("\n Average : (",
sum ,"/", totalNode ,") = ",
(Double(sum) / Double(totalNode)) ," ");
if (totalNode == 0)
{
self.average = self.maxValue(
self.average, Double(sum)
);
}
else
{
self.average = self.maxValue(
self.average, Double(sum) / Double(totalNode)
);
}
return sum;
}
// Handles the request to find average of max subtree
func maxAverage()
{
if (self.root == nil)
{
return;
}
self.average = -Double.greatestFiniteMagnitude;
self.count = 0;
let _ = self.findMaxAverage(self.root);
// Display final result
print("\n Result : ", self.average, terminator: "");
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree.root = TreeNode(4);
tree.root!.left = TreeNode(-4);
tree.root!.right = TreeNode(7);
tree.root!.right!.right = TreeNode(12);
tree.root!.right!.right!.left = TreeNode(15);
tree.root!.left!.right = TreeNode(30);
tree.root!.left!.right!.right = TreeNode(18);
tree.root!.left!.right!.left = TreeNode(15);
tree.root!.left!.left = TreeNode(2);
tree.root!.left!.left!.left = TreeNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
tree.maxAverage();
}
main();
Output
Node : 19 , [left subtree sum : 0 , right subtree sum : 0 ]
Total Node : 1
Average : ( 19 / 1 ) = 19.0
Node : 2 , [left subtree sum : 19 , right subtree sum : 0 ]
Total Node : 2
Average : ( 21 / 2 ) = 10.5
Node : 15 , [left subtree sum : 0 , right subtree sum : 0 ]
Total Node : 1
Average : ( 15 / 1 ) = 15.0
Node : 18 , [left subtree sum : 0 , right subtree sum : 0 ]
Total Node : 1
Average : ( 18 / 1 ) = 18.0
Node : 30 , [left subtree sum : 15 , right subtree sum : 18 ]
Total Node : 3
Average : ( 63 / 3 ) = 21.0
Node : -4 , [left subtree sum : 21 , right subtree sum : 63 ]
Total Node : 6
Average : ( 80 / 6 ) = 13.3333333333333
Node : 15 , [left subtree sum : 0 , right subtree sum : 0 ]
Total Node : 1
Average : ( 15 / 1 ) = 15.0
Node : 12 , [left subtree sum : 15 , right subtree sum : 0 ]
Total Node : 2
Average : ( 27 / 2 ) = 13.5
Node : 7 , [left subtree sum : 0 , right subtree sum : 27 ]
Total Node : 3
Average : ( 34 / 3 ) = 11.3333333333333
Node : 4 , [left subtree sum : 80 , right subtree sum : 34 ]
Total Node : 10
Average : ( 118 / 10 ) = 11.8
Result : 21.0
/*
Kotlin program for
Find the minimum leaf node in a binary tree
*/
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
var count: Int;
var average: Double;
constructor()
{
this.root = null;
this.count = 0;
this.average = 0.0;
}
fun maxValue(a: Double, b: Double): Double
{
if (a > b)
{
return a;
}
return b;
}
fun findMaxAverage(node: TreeNode ? ): Int
{
if (node == null)
{
return 0;
}
val back: Int = this.count;
this.count += 1;
// Sum of left and right sub tree
val lSum: Int = this.findMaxAverage(node.left);
val rSum: Int = this.findMaxAverage(node.right);
// Calculate sum of subtree nodes
val sum: Int = lSum + rSum + node.data;
val totalNode: Int = this.count - back;
// Display calculated operation
print("\n Node : " + node.data +
" + [left subtree sum : " +
lSum + " + right subtree sum : " + rSum + " ] ");
print("\n Total Node : " + totalNode);
print("\n Average : (" +
sum + "/" + totalNode + ") = " +
(sum.toDouble() / totalNode) + " \n");
if (totalNode == 0)
{
this.average = this.maxValue(
this.average, sum.toDouble()
);
}
else
{
this.average = this.maxValue(
this.average, sum.toDouble() / totalNode
);
}
return sum;
}
// Handles the request to find average of max subtree
fun maxAverage(): Unit
{
if (this.root == null)
{
return;
}
this.average = -Double.MAX_VALUE;
this.count = 0;
this.findMaxAverage(this.root);
// Display final result
print("\n Result : " + this.average);
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
4
/ \
-4 7
/ \ \
2 30 12
/ / \ /
19 15 18 15
-----------------
Binary tree
*/
tree.root = TreeNode(4);
tree.root?.left = TreeNode(-4);
tree.root?.right = TreeNode(7);
tree.root?.right?.right = TreeNode(12);
tree.root?.right?.right?.left = TreeNode(15);
tree.root?.left?.right = TreeNode(30);
tree.root?.left?.right?.right = TreeNode(18);
tree.root?.left?.right?.left = TreeNode(15);
tree.root?.left?.left = TreeNode(2);
tree.root?.left?.left?.left = TreeNode(19);
// Max subtree
// [30+15+18] / 3 = (63 /3 ) = 21
// Here 3 indicates number of nodes
tree.maxAverage();
}
Output
Node : 19 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (19/1) = 19.0
Node : 2 + [left subtree sum : 19 + right subtree sum : 0 ]
Total Node : 2
Average : (21/2) = 10.5
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.0
Node : 18 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (18/1) = 18.0
Node : 30 + [left subtree sum : 15 + right subtree sum : 18 ]
Total Node : 3
Average : (63/3) = 21.0
Node : -4 + [left subtree sum : 21 + right subtree sum : 63 ]
Total Node : 6
Average : (80/6) = 13.333333333333334
Node : 15 + [left subtree sum : 0 + right subtree sum : 0 ]
Total Node : 1
Average : (15/1) = 15.0
Node : 12 + [left subtree sum : 15 + right subtree sum : 0 ]
Total Node : 2
Average : (27/2) = 13.5
Node : 7 + [left subtree sum : 0 + right subtree sum : 27 ]
Total Node : 3
Average : (34/3) = 11.333333333333334
Node : 4 + [left subtree sum : 80 + right subtree sum : 34 ]
Total Node : 10
Average : (118/10) = 11.8
Result : 21.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